{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #二叉树的序列化与反序列化"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Hard"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #tree #depth-first-search #breadth-first-search #design #string #binary-tree"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #树 #深度优先搜索 #广度优先搜索 #设计 #字符串 #二叉树"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: Codec"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #二叉树的序列化与反序列化"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>序列化是将一个数据结构或者对象转换为连续的比特位的操作，进而可以将转换后的数据存储在一个文件或者内存中，同时也可以通过网络传输到另一个计算机环境，采取相反方式重构得到原数据。</p>\n",
    "\n",
    "<p>请设计一个算法来实现二叉树的序列化与反序列化。这里不限定你的序列 / 反序列化算法执行逻辑，只需要保证一个二叉树可以被序列化为一个字符串并且将这个字符串反序列化为原始的树结构。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<p><img alt=\"\" src=\"https://assets.leetcode.com/uploads/2020/09/15/serdeser.jpg\" style=\"width: 442px; height: 324px;\" /></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>root = [1,2,3,null,null,4,5]\n",
    "<strong>输出：</strong>[1,2,3,null,null,4,5]\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>root = []\n",
    "<strong>输出：</strong>[]\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 3：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>root = [1]\n",
    "<strong>输出：</strong>[1]\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 4：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>root = [1,2]\n",
    "<strong>输出：</strong>[1,2]\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li>输入输出格式与 LeetCode 目前使用的方式一致，详情请参阅&nbsp;<a href=\"/faq/#binary-tree\">LeetCode 序列化二叉树的格式</a>。你并非必须采取这种方式，也可以采用其他的方法解决这个问题。</li>\n",
    "\t<li>树中结点数在范围 <code>[0, 10<sup>4</sup>]</code> 内</li>\n",
    "\t<li><code>-1000 &lt;= Node.val &lt;= 1000</code></li>\n",
    "</ul>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><meta charset=\"UTF-8\" />注意：本题与主站 297&nbsp;题相同：<a href=\"https://leetcode-cn.com/problems/serialize-and-deserialize-binary-tree/\">https://leetcode-cn.com/problems/serialize-and-deserialize-binary-tree/</a>&nbsp;</p>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [h54YBf](https://leetcode.cn/problems/h54YBf/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [h54YBf](https://leetcode.cn/problems/h54YBf/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[1,2,3,null,null,4,5]', '[]', '[1]', '[1,2]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode(object):\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "from collections import deque\n",
    "\n",
    "class Codec:\n",
    "    def serialize(self, root):\n",
    "        if not root:\n",
    "            return 'None'\n",
    "        root.left = self.serialize(root.left)\n",
    "        root.right = self.serialize(root.right)\n",
    "        return f\"{root.val},{root.left},{root.right}\"\n",
    "\n",
    "    def deserialize(self, data):\n",
    "        dq = deque(data.split(','))\n",
    "\n",
    "        def dfs(li):\n",
    "            val = li.popleft()\n",
    "            if val == \"None\":\n",
    "                return None\n",
    "            root = TreeNode(int(val))\n",
    "            root.left = dfs(li)\n",
    "            root.right = dfs(li)\n",
    "            return root\n",
    "        return dfs(dq)\n",
    "\n",
    "        \n",
    "\n",
    "# Your Codec object will be instantiated and called as such:\n",
    "# ser = Codec()\n",
    "# deser = Codec()\n",
    "# ans = deser.deserialize(ser.serialize(root))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import deque\n",
    "\n",
    "class Codec:\n",
    "    def serialize(self, root):\n",
    "        if not root:\n",
    "            return 'None'\n",
    "        root.left = self.serialize(root.left)\n",
    "        root.right = self.serialize(root.right)\n",
    "        return f\"{root.val},{root.left},{root.right}\"\n",
    "\n",
    "    def deserialize(self, data):\n",
    "        dq = deque(data.split(','))\n",
    "\n",
    "        def dfs(li):\n",
    "            val = li.popleft()\n",
    "            if val == \"None\":\n",
    "                return None\n",
    "            root = TreeNode(int(val))\n",
    "            root.left = dfs(li)\n",
    "            root.right = dfs(li)\n",
    "            return root\n",
    "        return dfs(dq)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode(object):\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "# class Codec:\n",
    "\n",
    "#     def serialize(self, root):\n",
    "#         if not root: return ''\n",
    "#         queue = deque([root])\n",
    "#         res = []\n",
    "#         while queue:\n",
    "#             node = queue.popleft()\n",
    "#             if node:\n",
    "#                 res.append(str(node.val))\n",
    "#                 queue.append(node.left)\n",
    "#                 queue.append(node.right)\n",
    "#             else:\n",
    "#                 res.append('None')\n",
    "#         return ','.join(res)\n",
    "        \n",
    "\n",
    "#     def deserialize(self, data):\n",
    "#         if not data: return []\n",
    "#         dataList = data.split(',')\n",
    "#         root = TreeNode(int(dataList[0]))\n",
    "#         queue = deque([root])\n",
    "#         i = 1\n",
    "#         while queue:\n",
    "#             node = queue.popleft()\n",
    "#             if dataList[i] != 'None':\n",
    "#                 node.left = TreeNode(int(dataList[i]))\n",
    "#                 queue.append(node.left)\n",
    "#             i += 1\n",
    "#             if dataList[i] != 'None':\n",
    "#                 node.right = TreeNode(int(dataList[i]))\n",
    "#                 queue.append(node.right)\n",
    "#             i += 1\n",
    "#         return root\n",
    "\n",
    "class Codec:\n",
    "\n",
    "    def serialize(self, root):\n",
    "        if not root: return 'None'\n",
    "        root.left = self.serialize(root.left)\n",
    "        root.right = self.serialize(root.right)\n",
    "        return f\"{root.val},{root.left},{root.right}\"\n",
    "        \n",
    "\n",
    "    def deserialize(self, data):\n",
    "        dataList = data.split(',')\n",
    "        queue = deque(dataList)\n",
    "        def dfs(q):\n",
    "            val = q.popleft()\n",
    "            if val == 'None':\n",
    "                return None\n",
    "            root = TreeNode(int(val))\n",
    "            root.left = dfs(q)\n",
    "            root.right = dfs(q)\n",
    "            return root\n",
    "        return dfs(queue)\n",
    "\n",
    "        \n",
    "\n",
    "# Your Codec object will be instantiated and called as such:\n",
    "# ser = Codec()\n",
    "# deser = Codec()\n",
    "# ans = deser.deserialize(ser.serialize(root))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode(object):\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Codec:\n",
    "\n",
    "    def serialize(self, root):\n",
    "        \"\"\"Encodes a tree to a single string.\n",
    "        \n",
    "        :type root: TreeNode\n",
    "        :rtype: str\n",
    "        \"\"\"\n",
    "        def f(root):\n",
    "            if root==None:\n",
    "                a.append(\"#,\")\n",
    "            else:\n",
    "                a.append(str(root.val)+',')\n",
    "                f(root.left)\n",
    "                f(root.right)\n",
    "        a = []\n",
    "        f(root)\n",
    "        return \"\".join(a)\n",
    "        \n",
    "\n",
    "    def deserialize(self, data):\n",
    "        \"\"\"Decodes your encoded data to tree.\n",
    "        \n",
    "        :type data: str\n",
    "        :rtype: TreeNode\n",
    "        \"\"\"\n",
    "        def g(vals,cnt):\n",
    "            cur = vals[cnt[0]]\n",
    "            cnt[0] += 1\n",
    "            if cur == \"#\":\n",
    "                return \n",
    "            else:\n",
    "                head = TreeNode(int(cur))\n",
    "                head.left = g(vals,cnt)\n",
    "                head.right = g(vals,cnt)\n",
    "            return head\n",
    "\n",
    "\n",
    "        vals = data.split(\",\")\n",
    "        cnt = [0]\n",
    "        return g(vals,cnt)\n",
    "\n",
    "        \n",
    "\n",
    "# Your Codec object will be instantiated and called as such:\n",
    "# ser = Codec()\n",
    "# deser = Codec()\n",
    "# ans = deser.deserialize(ser.serialize(root))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode(object):\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Codec:\n",
    "    \n",
    "    sep = ','\n",
    "    NULL = '#'\n",
    "\n",
    "    def serialize(self, root):\n",
    "        \"\"\"Encodes a tree to a single string.\n",
    "        \n",
    "        :type root: TreeNode\n",
    "        :rtype: str\n",
    "        \"\"\"\n",
    "        res = []\n",
    "        if not root:\n",
    "            return ''\n",
    "        \n",
    "        q = [root]\n",
    "        while q:\n",
    "            sz = len(q)\n",
    "            for i in range(sz):\n",
    "                cur = q.pop(0)\n",
    "\n",
    "                if not cur:\n",
    "                    res.append(self.NULL)\n",
    "                    continue\n",
    "                res.append(str(cur.val))\n",
    "\n",
    "                q.append(cur.left)\n",
    "                q.append(cur.right)\n",
    "        \n",
    "\n",
    "        return self.sep.join(res)\n",
    "\n",
    "\n",
    "    def deserialize(self, data):\n",
    "        \"\"\"Decodes your encoded data to tree.\n",
    "        \n",
    "        :type data: str\n",
    "        :rtype: TreeNode\n",
    "        \"\"\"\n",
    "        if not data:\n",
    "            return None\n",
    "        nodes = data.split(self.sep)\n",
    "        root = TreeNode(int(nodes[0]))\n",
    "        q = [root]\n",
    "        i = 1\n",
    "        while i < len(nodes):\n",
    "            node = q.pop(0)\n",
    "            if nodes[i] != self.NULL:\n",
    "                node.left = TreeNode(int(nodes[i]))\n",
    "                q.append(node.left)\n",
    "            i += 1\n",
    "            if i < len(nodes) and nodes[i] != self.NULL:\n",
    "                node.right = TreeNode(int(nodes[i]))\n",
    "                q.append(node.right)\n",
    "            i += 1\n",
    "        return root\n",
    "\n",
    "\n",
    "# Your Codec object will be instantiated and called as such:\n",
    "# ser = Codec()\n",
    "# deser = Codec()\n",
    "# ans = deser.deserialize(ser.serialize(root))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode(object):\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Codec:\n",
    "    def __init__(self):\n",
    "        self.res = \"\"\n",
    "        self.i = 0\n",
    "\n",
    "    def traversal(self, root):\n",
    "        if not root:\n",
    "            self.res+= \"#,\"     \n",
    "        else:\n",
    "            self.res += str(root.val)+\",\"\n",
    "            self.traversal(root.left)\n",
    "            self.traversal(root.right)\n",
    "    def serialize(self, root):\n",
    "        \"\"\"Encodes a tree to a single string.\n",
    "        \n",
    "        :type root: TreeNode\n",
    "        :rtype: str\n",
    "        \"\"\"\n",
    "        self.traversal(root)\n",
    "        return self.res\n",
    "        \n",
    "    def dfs(self, listOfString):\n",
    "        if listOfString[self.i] == \"#\":\n",
    "            self.i+=1\n",
    "            return None\n",
    "        node = TreeNode(int(listOfString[self.i]))\n",
    "        self.i+=1\n",
    "        node.left = self.dfs(listOfString)\n",
    "        node.right = self.dfs(listOfString)\n",
    "        return node\n",
    "\n",
    "    def deserialize(self, data):\n",
    "        \"\"\"Decodes your encoded data to tree.\n",
    "        \n",
    "        :type data: str\n",
    "        :rtype: TreeNode\n",
    "        \"\"\"\n",
    "        listOfString = data.split(\",\")\n",
    "        return self.dfs(listOfString)\n",
    "        \n",
    "\n",
    "# Your Codec object will be instantiated and called as such:\n",
    "# ser = Codec()\n",
    "# deser = Codec()\n",
    "# ans = deser.deserialize(ser.serialize(root))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode(object):\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Codec:\n",
    "\n",
    "    def serialize(self, root):\n",
    "        \"\"\"Encodes a tree to a single string.\n",
    "        \n",
    "        :type root: TreeNode\n",
    "        :rtype: str\n",
    "        \"\"\"\n",
    "        self.alist = []\n",
    "        def preorder(root):\n",
    "            if not root:\n",
    "                self.alist.append('#')\n",
    "                return \n",
    "            self.alist.append(str(root.val))\n",
    "            preorder(root.left)\n",
    "            preorder(root.right)\n",
    "        preorder(root)\n",
    "        return ','.join(self.alist)\n",
    "\n",
    "\n",
    "\n",
    "    def deserialize(self, data):\n",
    "        \"\"\"Decodes your encoded data to tree.\n",
    "        \n",
    "        :type data: str\n",
    "        :rtype: TreeNode\n",
    "        \"\"\"\n",
    "        arr = data.split(',')\n",
    "        alen = len(arr)\n",
    "        if alen == 2:return None\n",
    "        return self.buildTree(arr)\n",
    "    \n",
    "    def buildTree(self,arr):\n",
    "        if arr[0] == '#':\n",
    "            arr.pop(0)\n",
    "            return None\n",
    "        root = TreeNode(int(arr[0]))\n",
    "        arr.pop(0)\n",
    "        root.left = self.buildTree(arr)\n",
    "        root.right = self.buildTree(arr)\n",
    "        return root\n",
    "\n",
    "\n",
    "\n",
    "# Your Codec object will be instantiated and called as such:\n",
    "# ser = Codec()\n",
    "# deser = Codec()\n",
    "# ans = deser.deserialize(ser.serialize(root))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode(object):\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Codec:\n",
    "\n",
    "    def serialize(self, root):\n",
    "        \"\"\"Encodes a tree to a single string.\n",
    "        \n",
    "        :type root: TreeNode\n",
    "        :rtype: str\n",
    "        \"\"\"\n",
    "        def f(root):\n",
    "            if root==None:\n",
    "                a.append(\"#,\")\n",
    "            else:\n",
    "                a.append(str(root.val)+',')\n",
    "                f(root.left)\n",
    "                f(root.right)\n",
    "        a = []\n",
    "        f(root)\n",
    "        return \"\".join(a)\n",
    "        \n",
    "\n",
    "    def deserialize(self, data):\n",
    "        \"\"\"Decodes your encoded data to tree.\n",
    "        \n",
    "        :type data: str\n",
    "        :rtype: TreeNode\n",
    "        \"\"\"\n",
    "        def g(vals,cnt):\n",
    "            \n",
    "            cur = vals[cnt[0]]\n",
    "            cnt[0] += 1\n",
    "            if cur == \"#\":\n",
    "                return\n",
    "            else:\n",
    "                head = TreeNode(int(cur))\n",
    "                head.left = g(vals,cnt)\n",
    "                head.right = g(vals,cnt)\n",
    "            return head\n",
    "        vals = data.split(',')\n",
    "        cnt = [0]\n",
    "        return g(vals,cnt)\n",
    "\n",
    "\n",
    "        \n",
    "\n",
    "# Your Codec object will be instantiated and called as such:\n",
    "# ser = Codec()\n",
    "# deser = Codec()\n",
    "# ans = deser.deserialize(ser.serialize(root))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode(object):\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Codec:\n",
    "\n",
    "    def serialize(self, root):\n",
    "        \"\"\"Encodes a tree to a single string.\n",
    "        :type root: TreeNode\n",
    "        :rtype: str\n",
    "        \"\"\"\n",
    "        if not root:\n",
    "            return \"\"\n",
    "        que = deque([root])\n",
    "        ans = []\n",
    "        while que:\n",
    "            node = que.popleft()\n",
    "            if node:\n",
    "                que.append(node.left)\n",
    "                que.append(node.right)\n",
    "                ans.append(str(node.val))\n",
    "            else:\n",
    "                ans.append('None')\n",
    "        return ','.join(ans)\n",
    "        \n",
    "\n",
    "    def deserialize(self, data):\n",
    "        \"\"\"Decodes your encoded data to tree.\n",
    "        \n",
    "        :type data: str\n",
    "        :rtype: TreeNode\n",
    "        \"\"\"\n",
    "        if not data:\n",
    "            return []\n",
    "        vallist = data.split(',')\n",
    "        root = TreeNode(int(vallist[0]))\n",
    "        dq = [root]\n",
    "        i = 1\n",
    "        while dq:\n",
    "            if vallist[i] != 'None':\n",
    "                dq[0].left = TreeNode(int(vallist[i]))\n",
    "                dq.append(dq[0].left)\n",
    "            i += 1\n",
    "            if vallist[i] != 'None':\n",
    "                dq[0].right = TreeNode(int(vallist[i]))\n",
    "                dq.append(dq[0].right)\n",
    "            i += 1\n",
    "            dq.pop(0)\n",
    "        return root\n",
    "            \n",
    "        \n",
    "\n",
    "# Your Codec object will be instantiated and called as such:\n",
    "# ser = Codec()\n",
    "# deser = Codec()\n",
    "# ans = deser.deserialize(ser.serialize(root))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode(object):\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Codec:\n",
    "\n",
    "    def serialize(self, root):\n",
    "        \"\"\"Encodes a tree to a single string.\n",
    "        \n",
    "        :type root: TreeNode\n",
    "        :rtype: str\n",
    "        \"\"\"\n",
    "        return self._serialize(root)\n",
    "    \n",
    "    def _serialize(self, node):\n",
    "        if not node:\n",
    "            return \"#\"\n",
    "        left = self._serialize(node.left)\n",
    "        right = self._serialize(node.right)\n",
    "        res = left + \",\" + right + \",\" + str(node.val)\n",
    "        return res\n",
    "\n",
    "    def deserialize(self, data):\n",
    "        \"\"\"Decodes your encoded data to tree.\n",
    "        \n",
    "        :type data: str\n",
    "        :rtype: TreeNode\n",
    "        \"\"\"\n",
    "        nodes = data.split(\",\")\n",
    "        return self._deserialize(nodes)\n",
    "    \n",
    "    def _deserialize(self, nodes):\n",
    "        if not nodes:\n",
    "            return\n",
    "        val = nodes.pop()\n",
    "        if val == \"#\":\n",
    "            return\n",
    "        root = TreeNode(val)\n",
    "        root.right = self._deserialize(nodes)\n",
    "        root.left = self._deserialize(nodes)\n",
    "        return root\n",
    "\n",
    "# Your Codec object will be instantiated and called as such:\n",
    "# ser = Codec()\n",
    "# deser = Codec()\n",
    "# ans = deser.deserialize(ser.serialize(root))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode(object):\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Codec:\n",
    "\n",
    "    def serialize(self, root):\n",
    "        \"\"\"Encodes a tree to a single string.\n",
    "        \n",
    "        :type root: TreeNode\n",
    "        :rtype: str\n",
    "        \"\"\"\n",
    "        if root is None:\n",
    "            return \"None\"\n",
    "        \n",
    "        return str(root.val) + ',' + self.serialize(root.left) + ',' + self.serialize(root.right)\n",
    "        \n",
    "\n",
    "    def deserialize(self, data):\n",
    "        \"\"\"Decodes your encoded data to tree.\n",
    "        \n",
    "        :type data: str\n",
    "        :rtype: TreeNode\n",
    "        \"\"\"\n",
    "        dataArray = data.split(',')\n",
    "        self.pos = 0\n",
    "        return self.rdeserialize(dataArray)\n",
    "        \n",
    "    def rdeserialize(self, dataArray: list[str]):\n",
    "        if dataArray[self.pos] == \"None\":\n",
    "            self.pos += 1\n",
    "            return None\n",
    "        \n",
    "        root = TreeNode(int(dataArray[self.pos]))\n",
    "        self.pos += 1\n",
    "        root.left = self.rdeserialize(dataArray)\n",
    "        root.right = self.rdeserialize(dataArray)\n",
    "        \n",
    "        return root\n",
    "\n",
    "# Your Codec object will be instantiated and called as such:\n",
    "# ser = Codec()\n",
    "# deser = Codec()\n",
    "# ans = deser.deserialize(ser.serialize(root))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode(object):\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Codec:\n",
    "\n",
    "    def serialize(self, root):\n",
    "        \"\"\"Encodes a tree to a single string.\n",
    "        \n",
    "        :type root: TreeNode\n",
    "        :rtype: str\n",
    "        \"\"\"\n",
    "        if root is None:\n",
    "            return 'None'\n",
    "\n",
    "        cur = str(root.val)\n",
    "        l = self.serialize(root.left)\n",
    "        r = self.serialize(root.right)\n",
    "        return cur+','+l+','+r\n",
    "        \n",
    "\n",
    "    def deserialize(self, data):\n",
    "        \"\"\"Decodes your encoded data to tree.\n",
    "        \n",
    "        :type data: str\n",
    "        :rtype: TreeNode\n",
    "        \"\"\"\n",
    "        node = data.split(',')\n",
    "        \n",
    "        def dfs():\n",
    "            cur = node.pop(0)\n",
    "            if cur=='None':\n",
    "                return None\n",
    "            root = TreeNode(int(cur))\n",
    "            root.left = dfs()\n",
    "            root.right = dfs()\n",
    "            return root\n",
    "\n",
    "        return dfs()\n",
    "        \n",
    "\n",
    "# Your Codec object will be instantiated and called as such:\n",
    "# ser = Codec()\n",
    "# deser = Codec()\n",
    "# ans = deser.deserialize(ser.serialize(root))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode(object):\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Codec:\n",
    "\n",
    "    def serialize(self, root):\n",
    "        \"\"\"Encodes a tree to a single string.\n",
    "        \n",
    "        :type root: TreeNode\n",
    "        :rtype: str\n",
    "        \"\"\"\n",
    "        if not root:\n",
    "            return \"\"\n",
    "        stack = [root]\n",
    "        res = []\n",
    "        while stack:\n",
    "            cur = stack.pop(0)\n",
    "            if cur:\n",
    "                res.append(str(cur.val))\n",
    "                stack.append(cur.left)\n",
    "                stack.append(cur.right)\n",
    "            else:\n",
    "                res.append(\"None\")\n",
    "        return ','.join(res)      \n",
    "\n",
    "    def deserialize(self, data):\n",
    "        \"\"\"Decodes your encoded data to tree.\n",
    "        \n",
    "        :type data: str\n",
    "        :rtype: TreeNode\n",
    "        \"\"\"\n",
    "        if not data:\n",
    "            return []\n",
    "        arr = data.split(',')\n",
    "        root = TreeNode(int(arr[0]))\n",
    "        stack = [root]\n",
    "       \n",
    "        i = 1\n",
    "        while stack:\n",
    "            cur_t = stack.pop(0)\n",
    "           \n",
    "            if arr[i]!='None':\n",
    "                \n",
    "                cur_t.left = TreeNode(arr[i])\n",
    "                stack.append(cur_t.left)\n",
    "            i+=1\n",
    "            if arr[i]!='None':\n",
    "              \n",
    "                cur_t.right = TreeNode(arr[i])\n",
    "                stack.append(cur_t.right)\n",
    "            i+=1\n",
    "        return root\n",
    "                \n",
    "                \n",
    "\n",
    "\n",
    "        \n",
    "\n",
    "        \n",
    "\n",
    "# Your Codec object will be instantiated and called as such:\n",
    "# ser = Codec()\n",
    "# deser = Codec()\n",
    "# ans = deser.deserialize(ser.serialize(root))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode(object):\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Codec:\n",
    "\n",
    "    def serialize(self, root):\n",
    "        if root is None:\n",
    "            return ''\n",
    "        res=[]\n",
    "        def preorder(root):\n",
    "            if root is None:\n",
    "                res.append('#,')\n",
    "                return \n",
    "            res.append(str(root.val)+\",\")\n",
    "            preorder(root.left)\n",
    "            preorder(root.right)\n",
    "        preorder(root)\n",
    "        return ''.join(res)\n",
    "        \n",
    "\n",
    "    def deserialize(self, data):\n",
    "        if not data:\n",
    "            return None\n",
    "        vals = data.split(',')\n",
    "        def inner():\n",
    "            first = vals.pop(0)\n",
    "            if first=='#':\n",
    "                return None\n",
    "            return TreeNode(int(first),inner(),inner())\n",
    "        return inner()\n",
    "        \n",
    "\n",
    "# Your Codec object will be instantiated and called as such:\n",
    "# ser = Codec()\n",
    "# deser = Codec()\n",
    "# ans = deser.deserialize(ser.serialize(root))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode(object):\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Codec:\n",
    "    def __init__(self):\n",
    "        self.NULL = '#'\n",
    "        self.SEQ = ','\n",
    "    \n",
    "    def serialize(self, root):\n",
    "        res = []\n",
    "        self.serialize_(root, res)\n",
    "        return ''.join(res)\n",
    "\n",
    "    def serialize_(self, root, res):\n",
    "        if not root:\n",
    "            res.append(self.NULL)\n",
    "            res.append(self.SEQ)\n",
    "            return\n",
    "        \n",
    "        res.append(str(root.val))\n",
    "        res.append(self.SEQ)\n",
    "\n",
    "        self.serialize_(root.left, res)\n",
    "        self.serialize_(root.right, res)\n",
    "\n",
    "    def deserialize(self, data):\n",
    "        nodes = data.split(self.SEQ)\n",
    "        return self.deserialize_(nodes)\n",
    "    \n",
    "    def deserialize_(self, nodes):\n",
    "        if not nodes:\n",
    "            return None\n",
    "        root_val = nodes.pop(0)\n",
    "        if root_val == self.NULL:\n",
    "            return None\n",
    "        root = TreeNode(root_val)\n",
    "        root.left = self.deserialize_(nodes)\n",
    "        root.right = self.deserialize_(nodes)\n",
    "\n",
    "        return root\n",
    "\n",
    "        \n",
    "        \n",
    "\n",
    "# Your Codec object will be instantiated and called as such:\n",
    "# ser = Codec()\n",
    "# deser = Codec()\n",
    "# ans = deser.deserialize(ser.serialize(root))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode(object):\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "from collections import deque\n",
    "class Codec:\n",
    "\n",
    "    def serialize(self, root):\n",
    "        \"\"\"Encodes a tree to a single string.\n",
    "        \n",
    "        :type root: TreeNode\n",
    "        :rtype: str\n",
    "        \"\"\"\n",
    "        queue = deque([root])\n",
    "        res = []\n",
    "        while queue:\n",
    "            node = queue.popleft()\n",
    "            if node:\n",
    "                res.append(str(node.val))\n",
    "                queue.append(node.left)\n",
    "                queue.append(node.right)\n",
    "            else:\n",
    "                res.append('')\n",
    "        return ','.join(res)\n",
    "\n",
    "\n",
    "    def deserialize(self, data):\n",
    "        \"\"\"Decodes your encoded data to tree.\n",
    "        \n",
    "        :type data: str\n",
    "        :rtype: TreeNode\n",
    "        \"\"\"\n",
    "        if not data:\n",
    "            return None\n",
    "        data = data.split(',')\n",
    "\n",
    "        root = TreeNode(int(data[0]))\n",
    "        queue = deque([root])\n",
    "        i = 1\n",
    "        while i < len(data):\n",
    "            node = queue.popleft()\n",
    "            val = data[i]\n",
    "            if val:\n",
    "                newNode = TreeNode(int(val))\n",
    "                node.left = newNode\n",
    "                queue.append(newNode)\n",
    "            i += 1\n",
    "\n",
    "            val = data[i]\n",
    "            if val:\n",
    "                newNode = TreeNode(int(val))\n",
    "                node.right = newNode\n",
    "                queue.append(newNode)\n",
    "            i += 1\n",
    "        return root\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "# Your Codec object will be instantiated and called as such:\n",
    "# ser = Codec()\n",
    "# deser = Codec()\n",
    "# ans = deser.deserialize(ser.serialize(root))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode(object):\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Codec:\n",
    "\n",
    "    def serialize(self, root):\n",
    "        \"\"\"Encodes a tree to a single string.\n",
    "        \n",
    "        :type root: TreeNode\n",
    "        :rtype: str\n",
    "        \"\"\"\n",
    "        def dfs(node):\n",
    "            if node==None:\n",
    "                preorder.append('null')\n",
    "                return\n",
    "            preorder.append(str(node.val))\n",
    "            dfs(node.left)\n",
    "            dfs(node.right)\n",
    "        preorder = []\n",
    "        dfs(root)\n",
    "        return ','.join(preorder)\n",
    "\n",
    "    def deserialize(self, data):\n",
    "        \"\"\"Decodes your encoded data to tree.\n",
    "        \n",
    "        :type data: str\n",
    "        :rtype: TreeNode\n",
    "        \"\"\"\n",
    "        preorder = data.split(',')\n",
    "        # preorder = collections.deque(preorder)\n",
    "        def dfs():\n",
    "            # if len(preorder)==0:\n",
    "            #     return\n",
    "            val = preorder.pop(0)\n",
    "            if val=='null':\n",
    "                return None\n",
    "            node = TreeNode(val)\n",
    "            node.left = dfs()\n",
    "            node.right = dfs()\n",
    "            return node\n",
    "        return dfs()\n",
    "        \n",
    "\n",
    "# Your Codec object will be instantiated and called as such:\n",
    "# ser = Codec()\n",
    "# deser = Codec()\n",
    "# ans = deser.deserialize(ser.serialize(root))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode(object):\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Codec:\n",
    "\n",
    "    def serialize(self, root):\n",
    "        \"\"\"Encodes a tree to a single string.\n",
    "        \n",
    "        :type root: TreeNode\n",
    "        :rtype: str\n",
    "        \"\"\"\n",
    "        q = []\n",
    "        res = []\n",
    "        if not root:\n",
    "            return res\n",
    "        q.append(root)\n",
    "        while q:\n",
    "            curr = q.pop(0)\n",
    "            \n",
    "            if curr != None:\n",
    "                res.append(str(curr.val))\n",
    "                q.append(curr.left)\n",
    "                q.append(curr.right)\n",
    "            else:\n",
    "                res.append('None')\n",
    "        return ','.join(res)\n",
    "                \n",
    "        \n",
    "\n",
    "    def deserialize(self, data):\n",
    "        \"\"\"Decodes your encoded data to tree.\n",
    "        \n",
    "        :type data: str\n",
    "        :rtype: TreeNode\n",
    "        \"\"\"\n",
    "        if not data:\n",
    "            return []\n",
    "        q = []\n",
    "        datal = data.split(',')\n",
    "        root = TreeNode(datal[0])\n",
    "        q.append(root)\n",
    "        idx = 1\n",
    "        while q:\n",
    "            curr = q.pop(0)\n",
    "            if datal[idx] != 'None':\n",
    "                curr.left = TreeNode(datal[idx])\n",
    "                q.append(curr.left)\n",
    "            idx += 1\n",
    "            if datal[idx] != 'None':\n",
    "                curr.right = TreeNode(datal[idx])\n",
    "                q.append(curr.right)\n",
    "            idx += 1\n",
    "        \n",
    "        return root\n",
    "            \n",
    "                \n",
    "        \n",
    "\n",
    "# Your Codec object will be instantiated and called as such:\n",
    "# ser = Codec()\n",
    "# deser = Codec()\n",
    "# ans = deser.deserialize(ser.serialize(root))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode(object):\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Codec:\n",
    "\n",
    "    def serialize(self, root):\n",
    "        \"\"\"Encodes a tree to a single string.\n",
    "        \n",
    "        :type root: TreeNode\n",
    "        :rtype: str\n",
    "        \"\"\"\n",
    "        if not root:\n",
    "            return ''\n",
    "        stack = [root]\n",
    "        res = []\n",
    "        while stack:\n",
    "            tmp = []\n",
    "            for s in stack:\n",
    "                if not s:\n",
    "                    res.extend(['#'])\n",
    "                else:\n",
    "                    res.append(str(s.val))\n",
    "                    tmp.extend([s.left, s.right])\n",
    "            stack = tmp\n",
    "        return ','.join(res)\n",
    "        \n",
    "\n",
    "    def deserialize(self, data):\n",
    "        \"\"\"Decodes your encoded data to tree.\n",
    "        \n",
    "        :type data: str\n",
    "        :rtype: TreeNode\n",
    "        \"\"\"\n",
    "        if data == '':\n",
    "            return None\n",
    "        data = data.split(',')\n",
    "        root = TreeNode(int(data[0]))\n",
    "        stack = [root]\n",
    "        length = len(data)\n",
    "        cur = 0\n",
    "        for i in range(1, length):\n",
    "            if i % 2 == 1:\n",
    "                cur = stack.pop(0)\n",
    "            if i % 2 == 1 and data[i] != '#':\n",
    "                cur.left = TreeNode(int(data[i]))\n",
    "                stack.append(cur.left)\n",
    "            elif i % 2 == 0 and data[i] != '#':\n",
    "                cur.right = TreeNode(int(data[i]))\n",
    "                stack.append(cur.right)\n",
    "        return root \n",
    "        \n",
    "\n",
    "# Your Codec object will be instantiated and called as such:\n",
    "# ser = Codec()\n",
    "# deser = Codec()\n",
    "# ans = deser.deserialize(ser.serialize(root))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode(object):\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Codec:\n",
    "\n",
    "    def serialize(self, root):\n",
    "        \"\"\"Encodes a tree to a single string.\n",
    "        \n",
    "        :type root: TreeNode\n",
    "        :rtype: str\n",
    "        \"\"\"\n",
    "        q = []\n",
    "        res = []\n",
    "        if not root:\n",
    "            return res\n",
    "        q.append(root)\n",
    "        while q:\n",
    "            curr = q.pop(0)\n",
    "            \n",
    "            if curr != None:\n",
    "                res.append(curr.val)\n",
    "                q.append(curr.left)\n",
    "                q.append(curr.right)\n",
    "            else:\n",
    "                res.append('None')\n",
    "        return res\n",
    "                \n",
    "        \n",
    "\n",
    "    def deserialize(self, data):\n",
    "        \"\"\"Decodes your encoded data to tree.\n",
    "        \n",
    "        :type data: str\n",
    "        :rtype: TreeNode\n",
    "        \"\"\"\n",
    "        if not data:\n",
    "            return []\n",
    "        q = []\n",
    "        root = TreeNode(data[0])\n",
    "        q.append(root)\n",
    "        idx = 1\n",
    "        while q:\n",
    "            curr = q.pop(0)\n",
    "            if data[idx] != 'None':\n",
    "                curr.left = TreeNode(data[idx])\n",
    "                q.append(curr.left)\n",
    "            idx += 1\n",
    "            if data[idx] != 'None':\n",
    "                curr.right = TreeNode(data[idx])\n",
    "                q.append(curr.right)\n",
    "            idx += 1\n",
    "        \n",
    "        return root\n",
    "            \n",
    "                \n",
    "        \n",
    "\n",
    "# Your Codec object will be instantiated and called as such:\n",
    "# ser = Codec()\n",
    "# deser = Codec()\n",
    "# ans = deser.deserialize(ser.serialize(root))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode(object):\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Codec:\n",
    "\n",
    "    def serialize(self, root):\n",
    "        if not root:\n",
    "            return \"\"\n",
    "        dq = deque([root])\n",
    "        res = []\n",
    "        while dq:\n",
    "            node = dq.popleft()\n",
    "            if node:\n",
    "                res.append(str(node.val))\n",
    "                dq.append(node.left)\n",
    "                dq.append(node.right)\n",
    "            else:\n",
    "                res.append('None')\n",
    "        return ','.join(res)\n",
    "\n",
    "    def deserialize(self, data):\n",
    "        if not data:\n",
    "            return []\n",
    "        dataList = data.split(',')\n",
    "        root = TreeNode(int(dataList[0]))\n",
    "        dq = deque([root])\n",
    "        i = 1\n",
    "        while dq:\n",
    "            node = dq.popleft()\n",
    "            if dataList[i] != 'None':\n",
    "                node.left = TreeNode(int(dataList[i]))\n",
    "                dq.append(node.left)\n",
    "            i += 1\n",
    "            if dataList[i] != 'None':\n",
    "                node.right = TreeNode(int(dataList[i]))\n",
    "                dq.append(node.right)\n",
    "            i += 1\n",
    "        return root"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode(object):\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Codec:\n",
    "    def serialize(self, root):\n",
    "        \"\"\"Encodes a tree to a single string.\n",
    "        :type root: TreeNode\n",
    "        :rtype: str\n",
    "        \"\"\"\n",
    "        if not root:\n",
    "            return ''\n",
    "        \n",
    "        queue = []\n",
    "        rst = []\n",
    "        queue.append(root)\n",
    "\n",
    "        while queue:\n",
    "            node = queue.pop(0)\n",
    "            if not node:\n",
    "                rst.append('#')\n",
    "            else:\n",
    "                rst.append(str(node.val))\n",
    "                queue.append(node.left)\n",
    "                queue.append(node.right)\n",
    "        \n",
    "        return ','.join(rst)\n",
    "            \n",
    "\n",
    "    def deserialize(self, data):\n",
    "        \"\"\"Decodes your encoded data to tree.\n",
    "        \n",
    "        :type data: str\n",
    "        :rtype: TreeNode\n",
    "        \"\"\"\n",
    "        \n",
    "        if data == '':\n",
    "            return None\n",
    "        \n",
    "        chars = data.split(',')\n",
    "        root = TreeNode(chars[0])\n",
    "        queue = []\n",
    "        queue.append(root)\n",
    "\n",
    "        i = 0\n",
    "        while queue:\n",
    "            node = queue.pop(0)\n",
    "            # 左            \n",
    "            i = i + 1\n",
    "            if chars[i] == '#':\n",
    "                node.left = None\n",
    "            else:\n",
    "                node.left = TreeNode(chars[i])\n",
    "                queue.append(node.left)\n",
    "        \n",
    "            # 右\n",
    "            i = i + 1\n",
    "            if chars[i] == '#':\n",
    "                node.right = None\n",
    "            else:\n",
    "                node.right = TreeNode(chars[i])\n",
    "                queue.append(node.right)\n",
    "\n",
    "        \n",
    "        return root\n",
    "# Your Codec object will be instantiated and called as such:\n",
    "# ser = Codec()\n",
    "# deser = Codec()\n",
    "# ans = deser.deserialize(ser.serialize(root))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode(object):\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Codec:\n",
    "\n",
    "    def serialize(self, root):\n",
    "        \"\"\"Encodes a tree to a single string.\n",
    "        \n",
    "        :type root: TreeNode\n",
    "        :rtype: str\n",
    "        \"\"\"\n",
    "        if not root:\n",
    "            return \"#\"\n",
    "        res=str(root.val)\n",
    "        res+=\",\"+self.serialize(root.left)\n",
    "        res+=\",\"+self.serialize(root.right)\n",
    "        return res\n",
    "\n",
    "    def deserialize(self, data):\n",
    "        \"\"\"Decodes your encoded data to tree.\n",
    "        \n",
    "        :type data: str\n",
    "        :rtype: TreeNode\n",
    "        \"\"\"\n",
    "        data=data.split(\",\")\n",
    "        data=data[::-1]\n",
    "        def construct(data):\n",
    "            if not data:\n",
    "                return None\n",
    "            tmp=data.pop()\n",
    "            if tmp==\"#\":\n",
    "                return None\n",
    "            root=TreeNode(int(tmp))\n",
    "            root.left=construct(data)\n",
    "            root.right=construct(data)\n",
    "\n",
    "            return root  \n",
    "\n",
    "        return construct(data)\n",
    "        \n",
    "\n",
    "# Your Codec object will be instantiated and called as such:\n",
    "# ser = Codec()\n",
    "# deser = Codec()\n",
    "# ans = deser.deserialize(ser.serialize(root))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode(object):\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Codec:\n",
    "\n",
    "    def serialize(self, root):\n",
    "        \"\"\"Encodes a tree to a single string.\n",
    "        \n",
    "        :type root: TreeNode\n",
    "        :rtype: strr\n",
    "        \"\"\"\n",
    "        res = \"\"\n",
    "        if (not root):\n",
    "            res += \"N,\"\n",
    "            # print (res)\n",
    "            return res\n",
    "\n",
    "        res += str(root.val) + ','\n",
    "        res += self.serialize(root.left)\n",
    "        res += self.serialize(root.right)\n",
    "        # print (res)\n",
    "        return res\n",
    "        \n",
    "    def subdeserialize(self, vals):\n",
    "        \"\"\"Decodes your encoded data to tree.\n",
    "        \n",
    "        :type vals: List(char) \n",
    "        :rtype: TreeNode\n",
    "        \"\"\"   \n",
    "        # print (vals)\n",
    "\n",
    "        cur = vals.pop(0)\n",
    "        if (cur == 'N'):\n",
    "            return None\n",
    "\n",
    "        root = TreeNode(int(cur))\n",
    "        root.left = self.subdeserialize(vals)\n",
    "        root.right = self.subdeserialize(vals)\n",
    "\n",
    "        return root\n",
    "\n",
    "\n",
    "    def deserialize(self, data):\n",
    "        \"\"\"Decodes your encoded data to tree.\n",
    "        \n",
    "        :type data: str\n",
    "        :rtype: TreeNode\n",
    "        \"\"\"\n",
    "        vals = data.split(\",\")\n",
    "        # print (vals)\n",
    "        return self.subdeserialize(vals[:-1])\n",
    "        \n",
    "\n",
    "# Your Codec object will be instantiated and called as such:\n",
    "# ser = Codec()\n",
    "# deser = Codec()\n",
    "# ans = deser.deserialize(ser.serialize(root))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Codec:\n",
    "    def serialize(self, root):\n",
    "        self.res = []\n",
    "        if not root:\n",
    "            return ''\n",
    "            \n",
    "        q = collections.deque()\n",
    "        q.append(root)\n",
    "        # 从上到下遍历二叉树的每一层\n",
    "        while q:\n",
    "            sz = len(q)\n",
    "            # 从左到右遍历每一层的每个节点\n",
    "            for i in range(sz):\n",
    "                cur = q.popleft()\n",
    "                if cur:\n",
    "                    self.res.append(str(cur.val))\n",
    "                    q.append(cur.left)\n",
    "                    q.append(cur.right)\n",
    "                else:\n",
    "                    self.res.append(\"null\")\n",
    "\n",
    "        self.res = ','.join(self.res)\n",
    "        return self.res\n",
    "    \n",
    "    def deserialize(self, data):\n",
    "        if data == '': \n",
    "            return None\n",
    "        vals, i = data.split(','), 1\n",
    "        root = TreeNode(int(vals[0]))\n",
    "        queue = collections.deque()\n",
    "        queue.append(root)\n",
    "        while queue:\n",
    "            node = queue.popleft()\n",
    "            if vals[i] != \"null\":\n",
    "                node.left = TreeNode(int(vals[i]))\n",
    "                queue.append(node.left)\n",
    "            i += 1\n",
    "            if vals[i] != \"null\":\n",
    "                node.right = TreeNode(int(vals[i]))\n",
    "                queue.append(node.right)\n",
    "            i += 1\n",
    "        return root"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode(object):\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "from collections import deque\n",
    "class Codec:\n",
    "\n",
    "    def serialize(self, root):\n",
    "        \"\"\"Encodes a tree to a single string.\n",
    "        \n",
    "        :type root: TreeNode\n",
    "        :rtype: str\n",
    "        \"\"\"\n",
    "        if not root:\n",
    "            return \"\"\n",
    "        ret=[]\n",
    "        dq=deque([root])\n",
    "        while dq:\n",
    "            node=dq.popleft()\n",
    "            if node:\n",
    "                ret.append(str(node.val))\n",
    "                dq.append(node.left)\n",
    "                dq.append(node.right)\n",
    "            else:\n",
    "                ret.append('None')\n",
    "        return ','.join(ret)\n",
    "\n",
    "    def deserialize(self, data):\n",
    "        \"\"\"Decodes your encoded data to tree.\n",
    "        \n",
    "        :type data: str\n",
    "        :rtype: TreeNode\n",
    "        \"\"\"\n",
    "        if not data:\n",
    "            return []\n",
    "        datalist=data.split(',')\n",
    "        root=TreeNode(int(datalist[0]))\n",
    "        dq=deque([root])\n",
    "        i=1\n",
    "        while dq:\n",
    "            node=dq.popleft()\n",
    "            if datalist[i] != 'None':\n",
    "                node.left = TreeNode(int(datalist[i]))\n",
    "                dq.append(node.left)\n",
    "            i+=1\n",
    "            if datalist[i] != 'None':\n",
    "                node.right = TreeNode(int(datalist[i]))\n",
    "                dq.append(node.right)\n",
    "            i+=1\n",
    "        return root\n",
    "            \n",
    "\n",
    "# Your Codec object will be instantiated and called as such:\n",
    "# ser = Codec()\n",
    "# deser = Codec()\n",
    "# ans = deser.deserialize(ser.serialize(root))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode(object):\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "from collections import deque\n",
    "class Codec:\n",
    "\n",
    "    def serialize(self, root):\n",
    "        \"\"\"Encodes a tree to a single string.\n",
    "        \n",
    "        :type root: TreeNode\n",
    "        :rtype: str\n",
    "        \"\"\"\n",
    "        if not root:\n",
    "            return \"\"\n",
    "        q = deque([root])\n",
    "        res = []\n",
    "        while q:\n",
    "            node = q.popleft()\n",
    "            \n",
    "            if node:\n",
    "                res.append(str(node.val))\n",
    "                q.append(node.left)\n",
    "                q.append(node.right)\n",
    "            else:\n",
    "                res.append('None')\n",
    "        return \",\".join(res)\n",
    "\n",
    "        \n",
    "\n",
    "    def deserialize(self, data):\n",
    "        \"\"\"Decodes your encoded data to tree.\n",
    "        \n",
    "        :type data: str\n",
    "        :rtype: TreeNode\n",
    "        \"\"\"\n",
    "        if not data:\n",
    "            return []\n",
    "        data_list = data.split(',')\n",
    "\n",
    "        root = TreeNode(int(data_list[0]))\n",
    "        i = 1\n",
    "        q = deque([root])\n",
    "        while q:\n",
    "            node = q.popleft()\n",
    "            if data_list[i]!='None':\n",
    "                left_node = TreeNode(int(data_list[i]))\n",
    "                node.left = left_node\n",
    "                q.append(left_node)\n",
    "            i+=1\n",
    "            if data_list[i]!='None':\n",
    "                right_node = TreeNode(int(data_list[i]))\n",
    "                node.right = right_node\n",
    "                q.append(right_node)\n",
    "            i += 1\n",
    "        return root\n",
    "\n",
    "        \n",
    "\n",
    "# Your Codec object will be instantiated and called as such:\n",
    "# ser = Codec()\n",
    "# deser = Codec()\n",
    "# ans = deser.deserialize(ser.serialize(root))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode(object):\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Codec:\n",
    "\n",
    "    def serialize(self, root):\n",
    "        \"\"\"Encodes a tree to a single string.\n",
    "        \n",
    "        :type root: TreeNode\n",
    "        :rtype: str\n",
    "        \"\"\"\n",
    "        if not root: return \"[]\"\n",
    "        res = []\n",
    "        queue = collections.deque([root])\n",
    "        while queue:\n",
    "            node = queue.popleft()\n",
    "            if node:\n",
    "                res.append(str(node.val))\n",
    "                queue.append(node.left)\n",
    "                queue.append(node.right)\n",
    "\n",
    "            else:\n",
    "                res.append(\"null\")\n",
    "\n",
    "        return \"[\" + \",\".join(res) + \"]\"\n",
    "\n",
    "        \n",
    "\n",
    "    def deserialize(self, data):\n",
    "        \"\"\"Decodes your encoded data to tree.\n",
    "        \n",
    "        :type data: str\n",
    "        :rtype: TreeNode\n",
    "        \"\"\"\n",
    "        if data == \"[]\": return\n",
    "        data = data[1:-1].split(\",\")\n",
    "        root = TreeNode(int(data[0]))\n",
    "        idx = 1\n",
    "        queue = collections.deque([root])\n",
    "        while queue:\n",
    "            node = queue.popleft()\n",
    "            if data[idx] != \"null\":\n",
    "                node.left = TreeNode(int(data[idx]))\n",
    "                queue.append(node.left)\n",
    "            idx += 1\n",
    "            if data[idx] != \"null\":\n",
    "                node.right = TreeNode(int(data[idx]))\n",
    "                queue.append(node.right)\n",
    "            idx += 1\n",
    "        \n",
    "        return root\n",
    "\n",
    "\n",
    "        \n",
    "\n",
    "\n",
    "\n",
    "# Your Codec object will be instantiated and called as such:\n",
    "# ser = Codec()\n",
    "# deser = Codec()\n",
    "# ans = deser.deserialize(ser.serialize(root))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode(object):\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Codec:\n",
    "    def serialize(self, root):\n",
    "        \"\"\"Encodes a tree to a single string.\n",
    "        \n",
    "        :type root: TreeNode\n",
    "        :rtype: str\n",
    "        \"\"\"\n",
    "        res = []\n",
    "        if not root:\n",
    "            return \"\"\n",
    "        deque = [root]\n",
    "        while deque:\n",
    "            node = deque.pop(0)\n",
    "            if node:\n",
    "                res.append(str(node.val))\n",
    "                deque.append(node.left)\n",
    "                deque.append(node.right)\n",
    "            else:\n",
    "                 res.append('None')\n",
    "        return ','.join(res)\n",
    "\n",
    "    def deserialize(self, data):\n",
    "        \"\"\"Decodes your encoded data to tree.\n",
    "        \n",
    "        :type data: str\n",
    "        :rtype: TreeNode\n",
    "        \"\"\"\n",
    "        if not data:\n",
    "            return []\n",
    "        data = data.split(',')\n",
    "        root = TreeNode(int(data[0]))\n",
    "        dp = [root]\n",
    "        if len(data) == 1:\n",
    "            return root\n",
    "        i = 1\n",
    "        while dp:\n",
    "            node = dp.pop(0)\n",
    "            if data[i] != 'None':\n",
    "                node.left = TreeNode(int(data[i]))\n",
    "                dp.append(node.left)\n",
    "            i += 1\n",
    "            if data[i] != 'None':\n",
    "                node.right = TreeNode(int(data[i]))\n",
    "                dp.append(node.right)\n",
    "            i += 1\n",
    "        return root\n",
    "\n",
    "        \n",
    "        \n",
    "\n",
    "# Your Codec object will be instantiated and called as such:\n",
    "# ser = Codec()\n",
    "# deser = Codec()\n",
    "# ans = deser.deserialize(ser.serialize(root))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode(object):\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Codec:\n",
    "    def __init__(self):\n",
    "        self.SEP = ','\n",
    "        self.NULL = '#'\n",
    "\n",
    "    def serialize(self, root):\n",
    "        \"\"\"Encodes a tree to a single string.\n",
    "        \n",
    "        :type root: TreeNode\n",
    "        :rtype: str\n",
    "        \"\"\"\n",
    "        sb = []\n",
    "        self._serialize(root, sb)\n",
    "        return ''.join(sb)\n",
    "    def _serialize(self, root, sb):\n",
    "        if not root:\n",
    "            sb.append(self.NULL)\n",
    "            sb.append(self.SEP)\n",
    "            return\n",
    "        sb.append(str(root.val))\n",
    "        sb.append(self.SEP)\n",
    "        self._serialize(root.left,sb)\n",
    "        self._serialize(root.right,sb)\n",
    "\n",
    "    def deserialize(self, data):\n",
    "        \"\"\"Decodes your encoded data to tree.\n",
    "        \n",
    "        :type data: str\n",
    "        :rtype: TreeNode\n",
    "        \"\"\"\n",
    "        nodes = data.split(self.SEP)\n",
    "        return self._deserialize(nodes)\n",
    "        \n",
    "    def _deserialize(self, nodes):\n",
    "        if not nodes:\n",
    "            return None\n",
    "        val = nodes.pop(0)\n",
    "        if val == self.NULL:\n",
    "            return None\n",
    "        root = TreeNode(val)\n",
    "        root.left = self._deserialize(nodes)\n",
    "        root.right = self._deserialize(nodes)\n",
    "        return root\n",
    "# Your Codec object will be instantiated and called as such:\n",
    "# ser = Codec()\n",
    "# deser = Codec()\n",
    "# ans = deser.deserialize(ser.serialize(root))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode(object):\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Codec:\n",
    "\n",
    "    def serialize(self, root):\n",
    "        \"\"\"Encodes a tree to a single string.\n",
    "        \n",
    "        :type root: TreeNode\n",
    "        :rtype: str\n",
    "        \"\"\"\n",
    "        if not root:\n",
    "            return \"#\"\n",
    "        self.s = \"\"\n",
    "        self.serializeFunction(root)\n",
    "        return self.s\n",
    "    def serializeFunction(self, root):\n",
    "        if not root:\n",
    "            self.s += \"#\"\n",
    "            return \n",
    "        \n",
    "        self.s += str(root.val) + \"!\"\n",
    "        self.serializeFunction(root.left)\n",
    "        self.serializeFunction(root.right) \n",
    "\n",
    "    def deserialize(self, data):\n",
    "        \"\"\"Decodes your encoded data to tree.\n",
    "        \n",
    "        :type data: str\n",
    "        :rtype: TreeNode\n",
    "        \"\"\"\n",
    "        self.index = 0\n",
    "        if data == \"#\":\n",
    "            return None\n",
    "        return self.deserializeFunction(data)\n",
    "\n",
    "    def deserializeFunction(self, data):\n",
    "        if self.index >= len(data) or data[self.index]==\"#\":\n",
    "            self.index += 1 # 跳过#号\n",
    "            return None\n",
    "        \n",
    "        val = 0\n",
    "        flag = False\n",
    "        while self.index < len(data) and data[self.index]!=\"!\":\n",
    "            if data[self.index] == \"-\":\n",
    "                flag = True\n",
    "            else:\n",
    "                val = val *10 + int(data[self.index])\n",
    "            self.index += 1\n",
    "        if flag:\n",
    "            val = (-1)*val \n",
    "        root = TreeNode(val)\n",
    "        \n",
    "        # 跳过分割的感叹号\n",
    "        if self.index == len(data):\n",
    "            return root\n",
    "        else:\n",
    "            self.index += 1\n",
    "\n",
    "        root.left = self.deserializeFunction(data)\n",
    "        root.right = self.deserializeFunction(data)\n",
    "\n",
    "        return root\n",
    "\n",
    "        \n",
    "\n",
    "# Your Codec object will be instantiated and called as such:\n",
    "# ser = Codec()\n",
    "# deser = Codec()\n",
    "# ans = deser.deserialize(ser.serialize(root))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode(object):\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Codec:\n",
    "\n",
    "    def serialize(self, root):\n",
    "        \"\"\"Encodes a tree to a single string.\n",
    "        \n",
    "        :type root: TreeNode\n",
    "        :rtype: str\n",
    "        \"\"\"\n",
    "        if not root: return []\n",
    "        res = []\n",
    "        queue = deque()\n",
    "        queue.append(root)\n",
    "        while queue:\n",
    "            cur_level_length = len(queue)\n",
    "            for _ in range(cur_level_length):\n",
    "                node = queue.popleft()\n",
    "                # 额外增加空值\n",
    "                if not node:\n",
    "                    res.append(None)\n",
    "                    continue\n",
    "                res.append(node.val)\n",
    "                queue.append(node.left)\n",
    "                queue.append(node.right)\n",
    "        \n",
    "        return res\n",
    "        \n",
    "\n",
    "    def deserialize(self, data):\n",
    "        \"\"\"Decodes your encoded data to tree.\n",
    "        \n",
    "        :type data: str\n",
    "        :rtype: TreeNode\n",
    "        \"\"\"\n",
    "        if not data: return None\n",
    "    \n",
    "        index = 0\n",
    "        val = data[index]\n",
    "        root = TreeNode(val)\n",
    "        queue = deque()\n",
    "        queue.append(root)\n",
    "        while queue:\n",
    "            node = queue.popleft()\n",
    "            # 左节点\n",
    "            if data[2 * index + 1] is not None:\n",
    "                node.left = TreeNode(data[2 * index + 1])\n",
    "                queue.append(node.left)\n",
    "            if data[2 * index + 2] is not None:\n",
    "                node.right = TreeNode(data[2 * index + 2])\n",
    "                queue.append(node.right)\n",
    "            \n",
    "            index += 1\n",
    "\n",
    "        return root\n",
    "        \n",
    "\n",
    "# Your Codec object will be instantiated and called as such:\n",
    "# ser = Codec()\n",
    "# deser = Codec()\n",
    "# ans = deser.deserialize(ser.serialize(root))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode(object):\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Codec:\n",
    "\n",
    "    def serialize(self, root):\n",
    "        \"\"\"Encodes a tree to a single string.\n",
    "        \n",
    "        :type root: TreeNode\n",
    "        :rtype: str\n",
    "        \"\"\"\n",
    "        ans = \"\"\n",
    "        def recurse(root):\n",
    "            nonlocal ans\n",
    "            if root == None:\n",
    "                ans += \",\" + \"None\"\n",
    "                return\n",
    "            ans += \",\" + str(root.val)\n",
    "            recurse(root.left)\n",
    "            recurse(root.right)\n",
    "        recurse(root)\n",
    "        return ans[1:]\n",
    "        \n",
    "\n",
    "    def deserialize(self, data):\n",
    "        \"\"\"Decodes your encoded data to tree.\n",
    "        \n",
    "        :type data: str\n",
    "        :rtype: TreeNode\n",
    "        \"\"\"\n",
    "        load = deque(data.split(','))\n",
    "        \n",
    "        def dfs(load):\n",
    "            v = load.popleft()\n",
    "            if v == 'None':\n",
    "                return None\n",
    "            root = TreeNode(int(v))\n",
    "            root.left = dfs(load)\n",
    "            root.right = dfs(load)\n",
    "            return root\n",
    "        return dfs(load)\n",
    "        \n",
    "\n",
    "# Your Codec object will be instantiated and called as such:\n",
    "# ser = Codec()\n",
    "# deser = Codec()\n",
    "# ans = deser.deserialize(ser.serialize(root))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode(object):\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Codec:\n",
    "    def serialize(self, root: Optional[TreeNode]) -> str:\n",
    "        ans = []\n",
    "        q = deque([root])\n",
    "        while q:\n",
    "            node = q.popleft()\n",
    "            if not node:\n",
    "                ans.append('x')\n",
    "                continue\n",
    "            ans.append(str(node.val))\n",
    "            q.append(node.left)\n",
    "            q.append(node.right)\n",
    "        return ','.join(ans)\n",
    "\n",
    "    def deserialize(self, data: str) -> Optional[TreeNode]:\n",
    "        vals = data.split(',')\n",
    "        if vals[0] == 'x':\n",
    "            return None\n",
    "        root = TreeNode(int(vals[0]))\n",
    "        q = deque([root])\n",
    "        for i in range(1, len(vals), 2):\n",
    "            lv, rv = vals[i], vals[i+1]\n",
    "            node = q.popleft()\n",
    "            if lv != 'x':\n",
    "                lchild = TreeNode(int(lv))\n",
    "                node.left = lchild\n",
    "                q.append(lchild)\n",
    "            if rv != 'x':\n",
    "                rchild = TreeNode(int(rv))\n",
    "                node.right = rchild\n",
    "                q.append(rchild)\n",
    "        return root\n",
    "\n",
    "\n",
    "# Your Codec object will be instantiated and called as such:\n",
    "# ser = Codec()\n",
    "# deser = Codec()\n",
    "# ans = deser.deserialize(ser.serialize(root))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode(object):\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "import queue\n",
    "\n",
    "\n",
    "\n",
    "class Codec:\n",
    "\n",
    "    def serialize(self, root):\n",
    "        \"\"\"Encodes a tree to a single string.\n",
    "\n",
    "        :type root: TreeNode\n",
    "        :rtype: str\n",
    "        \"\"\"\n",
    "        q = queue.Queue()\n",
    "        if not root:\n",
    "            return \"\"\n",
    "        q.put(root)\n",
    "        result = \"\"\n",
    "\n",
    "        while not q.empty():\n",
    "            # print(q.queue)\n",
    "            curnode = q.get()\n",
    "\n",
    "            if result!=\"\":\n",
    "                result += \",\"\n",
    "            if not curnode:\n",
    "                result += \"None\"\n",
    "            else:\n",
    "                result += str(curnode.val)\n",
    "                q.put(curnode.left)\n",
    "                q.put(curnode.right)\n",
    "        return result\n",
    "\n",
    "    def deserialize(self, data):\n",
    "        \"\"\"Decodes your encoded data to tree.\n",
    "\n",
    "        :type data: str\n",
    "        :rtype: TreeNode\n",
    "        \"\"\"\n",
    "        l = data.split(\",\")\n",
    "        print(l)\n",
    "        q = queue.Queue()\n",
    "\n",
    "        if len(l)==1:\n",
    "            return None\n",
    "        root = TreeNode(int(l[0]))\n",
    "        q.put(root)\n",
    "\n",
    "        num = 1\n",
    "        while not q.empty():\n",
    "            curnode = q.get()\n",
    "            if curnode:\n",
    "                curnode.left = TreeNode(int(l[num])) if l[num]!=\"None\" else None\n",
    "                q.put(curnode.left)\n",
    "                curnode.right = TreeNode(int(l[num+1])) if l[num+1]!=\"None\" else None\n",
    "                q.put(curnode.right)\n",
    "                num += 2\n",
    "        return root\n",
    "\n",
    "\n",
    "# Your Codec object will be instantiated and called as such:\n",
    "# ser = Codec()\n",
    "# deser = Codec()\n",
    "# ans = deser.deserialize(ser.serialize(root))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode(object):\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "from queue import Queue\n",
    "\n",
    "\n",
    "class Codec:\n",
    "\n",
    "    none_node_flag = \"#\"\n",
    "\n",
    "    def serialize(self, root: TreeNode):\n",
    "        \"\"\"Encodes a tree to a single string.\n",
    "        \n",
    "        :type root: TreeNode\n",
    "        :rtype: str\n",
    "        \"\"\"\n",
    "        path = []\n",
    "\n",
    "        def dfs(node: TreeNode):\n",
    "            if not node:\n",
    "                path.append(self.none_node_flag)\n",
    "                return\n",
    "            path.append(str(node.val))\n",
    "            dfs(node.left)\n",
    "            dfs(node.right)\n",
    "        dfs(root)\n",
    "        return \",\".join(path)\n",
    "\n",
    "    def deserialize(self, data: str):\n",
    "        \"\"\"Decodes your encoded data to tree.\n",
    "        \n",
    "        :type data: str\n",
    "        :rtype: TreeNode\n",
    "        \"\"\"\n",
    "        q = Queue()\n",
    "        for val in data.split(\",\"):\n",
    "            q.put(val)\n",
    "\n",
    "        def build() -> Optional[TreeNode]:\n",
    "            if q.qsize() == 0:\n",
    "                return None\n",
    "            val = q.get()\n",
    "            if val == self.none_node_flag:\n",
    "                return None\n",
    "            node = TreeNode(val)\n",
    "            node.left = build()\n",
    "            node.right = build()\n",
    "            return node\n",
    "        return build()\n",
    "\n",
    "# Your Codec object will be instantiated and called as such:\n",
    "# ser = Codec()\n",
    "# deser = Codec()\n",
    "# ans = deser.deserialize(ser.serialize(root))\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode(object):\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "import json\n",
    "\n",
    "\n",
    "class Codec:\n",
    "\n",
    "    def serialize(self, root):\n",
    "        \"\"\"Encodes a tree to a single string.\n",
    "        \n",
    "        :type root: TreeNode\n",
    "        :rtype: str\n",
    "        \"\"\"\n",
    "        return json.dumps(self.serialize_impl(root))\n",
    "\n",
    "    def deserialize(self, data):\n",
    "        \"\"\"Decodes your encoded data to tree.\n",
    "        \n",
    "        :type data: str\n",
    "        :rtype: TreeNode\n",
    "        \"\"\"\n",
    "        return self.deserialize_impl(json.loads(data))\n",
    "\n",
    "    def serialize_impl(self, root: TreeNode) -> List:\n",
    "        if root is None:\n",
    "            return []\n",
    "        vals = [root.val]\n",
    "        if root.left is not None:\n",
    "            vals.append(self.serialize_impl(root.left))\n",
    "        elif root.right is not None:\n",
    "            vals.append(None)\n",
    "        if root.right is not None:\n",
    "            vals.append(self.serialize_impl(root.right))\n",
    "        return vals\n",
    "\n",
    "    def deserialize_impl(self, vals: List) -> TreeNode:\n",
    "        if vals is None or len(vals) == 0:\n",
    "            return None\n",
    "        root = TreeNode(vals[0])\n",
    "        if len(vals) >= 2:\n",
    "            root.left = self.deserialize_impl(vals[1])\n",
    "        if len(vals) >= 3:\n",
    "            root.right = self.deserialize_impl(vals[2])\n",
    "        return root\n",
    "\n",
    "# Your Codec object will be instantiated and called as such:\n",
    "# ser = Codec()\n",
    "# deser = Codec()\n",
    "# ans = deser.deserialize(ser.serialize(root))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode(object):\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Codec:\n",
    "\n",
    "    def serialize(self, root):\n",
    "        \"\"\"Encodes a tree to a single string.\n",
    "        \n",
    "        :type root: TreeNode\n",
    "        :rtype: str\n",
    "        \"\"\"\n",
    "        if not root:\n",
    "            return 'None'\n",
    "        return str(root.val) + ',' + self.serialize(root.left) + ',' + self.serialize(root.right)\n",
    "        \n",
    "\n",
    "    def deserialize(self, data):\n",
    "        \"\"\"Decodes your encoded data to tree.\n",
    "        \n",
    "        :type data: str\n",
    "        :rtype: TreeNode\n",
    "        \"\"\"\n",
    "        def dfs(datalist):\n",
    "            val = datalist.popleft()\n",
    "            if val == 'None':\n",
    "                return None\n",
    "            root = TreeNode(val)\n",
    "            root.left = dfs(datalist)\n",
    "            root.right = dfs(datalist)\n",
    "            return root\n",
    "        \n",
    "        datalist = collections.deque(data.split(','))\n",
    "        return dfs(datalist)\n",
    "        \n",
    "\n",
    "# Your Codec object will be instantiated and called as such:\n",
    "# ser = Codec()\n",
    "# deser = Codec()\n",
    "# ans = deser.deserialize(ser.serialize(root))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode(object):\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Codec:\n",
    "\n",
    "    def serialize(self, root):\n",
    "        \"\"\"Encodes a tree to a single string.\n",
    "        \n",
    "        :type root: TreeNode\n",
    "        :rtype: str\n",
    "        \"\"\"\n",
    "        #前序遍历\n",
    "        if not root: return \"[]\"\n",
    "        queue = collections.deque()\n",
    "        res = []\n",
    "        queue.append(root)\n",
    "        while queue:\n",
    "            n = len(queue)\n",
    "            ans = []\n",
    "            for i in range(n):\n",
    "                node = queue.popleft()\n",
    "                if node:\n",
    "                    res.append(str(node.val))\n",
    "                    ans.append(node.left)\n",
    "                    ans.append(node.right)\n",
    "                else:\n",
    "                    res.append(str(None))\n",
    "            queue.extend(ans)\n",
    "        self.serialized_data = \"#\".join(res)         \n",
    "        # print(self.serialized_data)\n",
    "        return self.serialized_data\n",
    "            \n",
    "        \n",
    "\n",
    "    def deserialize(self, data):\n",
    "        \"\"\"Decodes your encoded data to tree.\n",
    "        \n",
    "        :type data: str\n",
    "        :rtype: TreeNode\n",
    "        \"\"\"\n",
    "        if data == \"[]\": return \n",
    "        da = data.split('#')\n",
    "        root = TreeNode(int(da[0]))\n",
    "        tree_queue = collections.deque()\n",
    "        tree_queue.append(root)\n",
    "        i = 1\n",
    "        while tree_queue:\n",
    "            node = tree_queue.popleft()\n",
    "            if da[i] != \"None\":\n",
    "                node.left = TreeNode(int(da[i]))\n",
    "                tree_queue.append(node.left)\n",
    "            i += 1\n",
    "            if da[i] != \"None\":\n",
    "                node.right = TreeNode(int(da[i]))\n",
    "                tree_queue.append(node.right)\n",
    "            i += 1\n",
    "        return root \n",
    "\n",
    "# Your Codec object will be instantiated and called as such:\n",
    "# ser = Codec()\n",
    "# deser = Codec()\n",
    "# ans = deser.deserialize(ser.serialize(root))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode(object):\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Codec:\n",
    "\n",
    "    def serialize(self, root):\n",
    "        \"\"\"Encodes a tree to a single string.\n",
    "        \n",
    "        :type root: TreeNode\n",
    "        :rtype: str\n",
    "        \"\"\"\n",
    "        if not root:\n",
    "            return \"\"\n",
    "        queue = deque([root])\n",
    "        res=\"\"\n",
    "        while queue:\n",
    "            node = queue.popleft()\n",
    "            if node:\n",
    "                res=res+str(node.val)+'_'\n",
    "                queue.append(node.left)\n",
    "                queue.append(node.right)\n",
    "            else:\n",
    "                res=res+\"None_\"\n",
    "        print(res)\n",
    "        return res[:-1]\n",
    "\n",
    "    def deserialize(self, data):\n",
    "        \"\"\"Decodes your encoded data to tree.\n",
    "        \n",
    "        :type data: str\n",
    "        :rtype: TreeNode\n",
    "        \"\"\"\n",
    "        if not data:\n",
    "            return None\n",
    "        datalist = data.split('_')\n",
    "        root = TreeNode(datalist[0])\n",
    "        queue = deque([root])\n",
    "        i = 1\n",
    "        print(datalist)\n",
    "        while queue:\n",
    "            node = queue.popleft()\n",
    "            if datalist[i] != 'None':\n",
    "                left=TreeNode(int(datalist[i]))\n",
    "                node.left=left\n",
    "                queue.append(left)\n",
    "            i+=1\n",
    "            if datalist[i] != 'None':\n",
    "                right=TreeNode(int(datalist[i]))\n",
    "                node.right=right\n",
    "                queue.append(right)\n",
    "            i+=1\n",
    "        return root\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "        \n",
    "\n",
    "# Your Codec object will be instantiated and called as such:\n",
    "# ser = Codec()\n",
    "# deser = Codec()\n",
    "# ans = deser.deserialize(ser.serialize(root))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode(object):\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Codec:\n",
    "\n",
    "    def serialize(self, root):\n",
    "        \"\"\"Encodes a tree to a single string.\n",
    "        \n",
    "        :type root: TreeNode\n",
    "        :rtype: str\n",
    "        \"\"\"\n",
    "        if not root: return \"[]\"\n",
    "        res = []\n",
    "        queue = collections.deque([root])\n",
    "        while queue:\n",
    "            node = queue.popleft()\n",
    "            if node:\n",
    "                res.append(str(node.val))\n",
    "                queue.append(node.left)\n",
    "                queue.append(node.right)\n",
    "\n",
    "            else:\n",
    "                res.append(\"null\")\n",
    "\n",
    "        return \"[\" + \",\".join(res) + \"]\"\n",
    "\n",
    "        \n",
    "\n",
    "    def deserialize(self, data):\n",
    "        \"\"\"Decodes your encoded data to tree.\n",
    "        \n",
    "        :type data: str\n",
    "        :rtype: TreeNode\n",
    "        \"\"\"\n",
    "        if data == \"[]\": return None\n",
    "        data = data[1:-1].split(\",\")\n",
    "        idx = 1\n",
    "        root = TreeNode(int(data[0]))\n",
    "        queue = collections.deque([root])\n",
    "        while queue:\n",
    "            node = queue.popleft()\n",
    "            if data[idx] != \"null\":\n",
    "                node.left = TreeNode(int(data[idx]))\n",
    "                queue.append(node.left)\n",
    "            idx += 1\n",
    "            if data[idx] != \"null\":\n",
    "                node.right = TreeNode(int(data[idx]))\n",
    "                queue.append(node.right)\n",
    "            idx += 1\n",
    "\n",
    "            if idx >= len(data): break\n",
    "        \n",
    "        return root\n",
    "\n",
    "        \n",
    "\n",
    "\n",
    "\n",
    "# Your Codec object will be instantiated and called as such:\n",
    "# ser = Codec()\n",
    "# deser = Codec()\n",
    "# ans = deser.deserialize(ser.serialize(root))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode(object):\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Codec:\n",
    "\n",
    "    def serialize(self, root):\n",
    "        \"\"\"Encodes a tree to a single string.\n",
    "        \n",
    "        :type root: TreeNode\n",
    "        :rtype: str\n",
    "        \"\"\"\n",
    "        if root == None:\n",
    "            return '#'\n",
    "        leftstr = self.serialize(root.left)\n",
    "        rightstr = self.serialize(root.right)\n",
    "        return str(root.val) + ',' + leftstr + ',' + rightstr\n",
    "\n",
    "    def deserialize(self, data):\n",
    "        \"\"\"Decodes your encoded data to tree.\n",
    "        \n",
    "        :type data: str\n",
    "        :rtype: TreeNode\n",
    "        \"\"\"\n",
    "        lser = data.split(',')\n",
    "        self.i = 0\n",
    "        return self.dfs(lser)\n",
    "\n",
    "    def dfs(self, liststr):\n",
    "        s = liststr[self.i]\n",
    "        self.i += 1\n",
    "        if s == '#':\n",
    "            return None\n",
    "        node = TreeNode(int(s))\n",
    "        node.left = self.dfs(liststr)\n",
    "        node.right = self.dfs(liststr)\n",
    "        return node\n",
    "\n",
    "        \n",
    "        \n",
    "\n",
    "# Your Codec object will be instantiated and called as such:\n",
    "# ser = Codec()\n",
    "# deser = Codec()\n",
    "# ans = deser.deserialize(ser.serialize(root))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode(object):\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Codec:\n",
    "\n",
    "    def serialize(self, root):\n",
    "        \"\"\"Encodes a tree to a single string.\n",
    "        \n",
    "        :type root: TreeNode\n",
    "        :rtype: str\n",
    "        \"\"\"\n",
    "        if not root:\n",
    "            return '#'\n",
    "        return str(root.val) + ' ' + self.serialize(root.left) + ' ' + self.serialize(root.right)\n",
    "        \n",
    "\n",
    "    def deserialize(self, data):\n",
    "        \"\"\"Decodes your encoded data to tree.\n",
    "        \n",
    "        :type data: str\n",
    "        :rtype: TreeNode\n",
    "        \"\"\"\n",
    "\n",
    "        def dfs(strs):\n",
    "            v = strs.pop(0)\n",
    "            if v == '#':\n",
    "                return None\n",
    "            \n",
    "            node = TreeNode(v)\n",
    "            node.left = dfs(strs)\n",
    "            node.right = dfs(strs)\n",
    "            return node\n",
    "\n",
    "        strs = data.split(' ')\n",
    "        return dfs(strs)\n",
    "        \n",
    "\n",
    "# Your Codec object will be instantiated and called as such:\n",
    "# ser = Codec()\n",
    "# deser = Codec()\n",
    "# ans = deser.deserialize(ser.serialize(root))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode(object):\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Codec:\n",
    "\n",
    "    def serialize(self, root):\n",
    "        \"\"\"Encodes a tree to a single string.\n",
    "        \n",
    "        :type root: TreeNode\n",
    "        :rtype: str\n",
    "        \"\"\"\n",
    "        if not root:\n",
    "            return \"\"\n",
    "        queue = deque([root])\n",
    "        res=\"\"\n",
    "        while queue:\n",
    "            node = queue.popleft()\n",
    "            if node:\n",
    "                res=res+str(node.val)+'_'\n",
    "                queue.append(node.left)\n",
    "                queue.append(node.right)\n",
    "            else:\n",
    "                res=res+\"None_\"\n",
    "        \n",
    "        return res[:-1]\n",
    "\n",
    "    def deserialize(self, data):\n",
    "        \"\"\"Decodes your encoded data to tree.\n",
    "        \n",
    "        :type data: str\n",
    "        :rtype: TreeNode\n",
    "        \"\"\"\n",
    "        if not data:\n",
    "            return None\n",
    "        datalist = data.split('_')\n",
    "        root = TreeNode(datalist[0])\n",
    "        queue = deque([root])\n",
    "        i = 1\n",
    "        \n",
    "        while queue:\n",
    "            node = queue.popleft()\n",
    "            if datalist[i] != 'None':\n",
    "                left=TreeNode(int(datalist[i]))\n",
    "                node.left=left\n",
    "                queue.append(left)\n",
    "            i+=1\n",
    "            if datalist[i] != 'None':\n",
    "                right=TreeNode(int(datalist[i]))\n",
    "                node.right=right\n",
    "                queue.append(right)\n",
    "            i+=1\n",
    "        return root\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "        \n",
    "\n",
    "# Your Codec object will be instantiated and called as such:\n",
    "# ser = Codec()\n",
    "# deser = Codec()\n",
    "# ans = deser.deserialize(ser.serialize(root))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode(object):\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Codec:\n",
    "    def serialize(self, root):\n",
    "        \"\"\"Encodes a tree to a single string.\n",
    "        \n",
    "        :type root: TreeNode\n",
    "        :rtype: str\n",
    "        \"\"\"\n",
    "        if not root:\n",
    "            return \"[]\"\n",
    "        queue = []\n",
    "        queue.append(root)\n",
    "        res = []\n",
    "        while queue:\n",
    "            node = queue.pop(0)\n",
    "            if node:\n",
    "                res.append(str(node.val))\n",
    "                queue.append(node.left)\n",
    "                queue.append(node.right)\n",
    "            else:\n",
    "                res.append(\"null\")\n",
    "        return \"[\" + \",\".join(res) + \"]\"\n",
    "\n",
    "    def deserialize(self, data):\n",
    "        \"\"\"Decodes your encoded data to tree.\n",
    "        \n",
    "        :type data: str\n",
    "        :rtype: TreeNode\n",
    "        \"\"\"\n",
    "        if data == \"[]\":\n",
    "            return None \n",
    "        vals = data[1:-1].split(\",\")\n",
    "        root = TreeNode(int(vals[0]))\n",
    "        queue = []\n",
    "        queue.append(root)\n",
    "\n",
    "        idx = 1\n",
    "        while queue:\n",
    "            node = queue.pop(0)\n",
    "            if vals[idx] != \"null\":\n",
    "                node.left = TreeNode(int(vals[idx]))\n",
    "                queue.append(node.left)\n",
    "            idx += 1\n",
    "            if vals[idx] != \"null\":\n",
    "                node.right = TreeNode(int(vals[idx]))\n",
    "                queue.append(node.right)\n",
    "            idx += 1\n",
    "        return root \n",
    "        \n",
    "\n",
    "# Your Codec object will be instantiated and called as such:\n",
    "# ser = Codec()\n",
    "# deser = Codec()\n",
    "# ans = deser.deserialize(ser.serialize(root))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode(object):\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Codec:\n",
    "\n",
    "    def serialize(self, root):\n",
    "        \"\"\"Encodes a tree to a single string.\n",
    "        \n",
    "        :type root: TreeNode\n",
    "        :rtype: str\n",
    "        \"\"\"\n",
    "        self.res = []\n",
    "        def traverse(root):\n",
    "            if root is None:\n",
    "                self.res.append(\"*\")\n",
    "                return\n",
    "            \n",
    "            self.res.append(str(root.val))\n",
    "            traverse(root.left)\n",
    "            traverse(root.right)\n",
    "        traverse(root)\n",
    "        return \",\".join(self.res)\n",
    "        \n",
    "\n",
    "    def deserialize(self, data):\n",
    "        \"\"\"Decodes your encoded data to tree.\n",
    "        \n",
    "        :type data: str\n",
    "        :rtype: TreeNode\n",
    "        \"\"\"\n",
    "        res = data.split(',')\n",
    "        print(res)\n",
    "        def build(res):\n",
    "            root_val = res.pop(0)\n",
    "            if root_val == \"*\":\n",
    "                return None\n",
    "            \n",
    "            root = TreeNode(int(root_val))\n",
    "            \n",
    "            root.left = build(res)\n",
    "            root.right = build(res)\n",
    "            return root\n",
    "        \n",
    "        return build(res)\n",
    "        \n",
    "\n",
    "# Your Codec object will be instantiated and called as such:\n",
    "# ser = Codec()\n",
    "# deser = Codec()\n",
    "# ans = deser.deserialize(ser.serialize(root))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode(object):\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Codec:\n",
    "\n",
    "    def serialize(self, root):\n",
    "        if not root: return ''\n",
    "        queue = deque([root])\n",
    "        res = []\n",
    "        while queue:\n",
    "            node = queue.popleft()\n",
    "            if node:\n",
    "                res.append(str(node.val))\n",
    "                queue.append(node.left)\n",
    "                queue.append(node.right)\n",
    "            else:\n",
    "                res.append('None')\n",
    "        return ','.join(res)\n",
    "        \n",
    "\n",
    "    def deserialize(self, data):\n",
    "        if not data: return []\n",
    "        dataList = data.split(',')\n",
    "        root = TreeNode(int(dataList[0]))\n",
    "        queue = deque([root])\n",
    "        i = 1\n",
    "        while queue:\n",
    "            node = queue.popleft()\n",
    "            if dataList[i] != 'None':\n",
    "                node.left = TreeNode(int(dataList[i]))\n",
    "                queue.append(node.left)\n",
    "            i += 1\n",
    "            if dataList[i] != 'None':\n",
    "                node.right = TreeNode(int(dataList[i]))\n",
    "                queue.append(node.right)\n",
    "            i += 1\n",
    "        return root\n",
    "\n",
    "\n",
    "        \n",
    "\n",
    "# Your Codec object will be instantiated and called as such:\n",
    "# ser = Codec()\n",
    "# deser = Codec()\n",
    "# ans = deser.deserialize(ser.serialize(root))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode(object):\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Codec:\n",
    "\n",
    "    def serialize(self, root):\n",
    "        \"\"\"Encodes a tree to a single string.\n",
    "        \n",
    "        :type root: TreeNode\n",
    "        :rtype: str\n",
    "        \"\"\"\n",
    "        res = []\n",
    "        def traverse(root):\n",
    "            if not root:\n",
    "                res.append(\"null\")\n",
    "                return\n",
    "            res.append(str(root.val))\n",
    "            traverse(root.left)\n",
    "            traverse(root.right)\n",
    "        traverse(root)\n",
    "        return \"#\".join(res)\n",
    "        \n",
    "\n",
    "    def deserialize(self, data):\n",
    "        \"\"\"Decodes your encoded data to tree.\n",
    "        \n",
    "        :type data: str\n",
    "        :rtype: TreeNode\n",
    "        \"\"\"\n",
    "        res = data.split(\"#\")[::-1]\n",
    "\n",
    "        def construct(res):\n",
    "            if not res:\n",
    "                return\n",
    "            root_val = res.pop()\n",
    "            if root_val == \"null\":\n",
    "                return\n",
    "            root = TreeNode(int(root_val))\n",
    "            root.left = construct(res)\n",
    "            root.right = construct(res)\n",
    "            return root\n",
    "        return construct(res)\n",
    "        \n",
    "\n",
    "# Your Codec object will be instantiated and called as such:\n",
    "# ser = Codec()\n",
    "# deser = Codec()\n",
    "# ans = deser.deserialize(ser.serialize(root))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode(object):\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Codec:\n",
    "\n",
    "    def serialize(self, root):\n",
    "        \"\"\"Encodes a tree to a single string.\n",
    "        \n",
    "        :type root: TreeNode\n",
    "        :rtype: str\n",
    "        \"\"\"\n",
    "        if not root: return \"*\"\n",
    "        return self.serialize(root.left) + \",\" + self.serialize(root.right) + \",\" + str(root.val)\n",
    "\n",
    "    def deserialize(self, data):\n",
    "        \"\"\"Decodes your encoded data to tree.\n",
    "        \n",
    "        :type data: str\n",
    "        :rtype: TreeNode\n",
    "        \"\"\"\n",
    "        return self.buildTree(data.split(\",\"))\n",
    "\n",
    "    def buildTree(self, nodes: List[str]) -> Optional[TreeNode]:\n",
    "        if not nodes: return None\n",
    "        nodeVal = nodes.pop()\n",
    "        if nodeVal == \"*\": return None\n",
    "        node = TreeNode(int(nodeVal))\n",
    "        node.right = self.buildTree(nodes)\n",
    "        node.left = self.buildTree(nodes)\n",
    "        return node\n",
    "        \n",
    "\n",
    "# Your Codec object will be instantiated and called as such:\n",
    "# ser = Codec()\n",
    "# deser = Codec()\n",
    "# ans = deser.deserialize(ser.serialize(root))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode(object):\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Codec:\n",
    "\n",
    "    def serialize(self, root):\n",
    "        \"\"\"Encodes a tree to a single string.\n",
    "        \n",
    "        :type root: TreeNode\n",
    "        :rtype: str\n",
    "        \"\"\"\n",
    "        return str(root.val) + \" \" + self.serialize(root.left) + \" \" + self.serialize(root.right) if root else \"null\"\n",
    "\n",
    "\n",
    "    def deserialize(self, data):\n",
    "        \"\"\"Decodes your encoded data to tree.\n",
    "        \n",
    "        :type data: str\n",
    "        :rtype: TreeNode\n",
    "        \"\"\"\n",
    "        valList = data.split()\n",
    "        p = 0\n",
    "        def dfs():\n",
    "            nonlocal p, valList\n",
    "            if valList[p] == 'null':\n",
    "                p += 1\n",
    "                return None\n",
    "            else:\n",
    "                r = TreeNode(int(valList[p]))\n",
    "                p += 1\n",
    "                r.left = dfs()\n",
    "                r.right = dfs()\n",
    "                return r\n",
    "\n",
    "        return dfs()\n",
    "\n",
    "# Your Codec object will be instantiated and called as such:\n",
    "# ser = Codec()\n",
    "# deser = Codec()\n",
    "# ans = deser.deserialize(ser.serialize(root))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode(object):\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "# https://mp.weixin.qq.com/s/DVX2A1ha4xSecEXLxW_UsA\n",
    "# 哦，原来前序遍历的意思是：先遍历根节点，再遍历左子树，最后遍历右子树\n",
    "# 本题考查：已知一个前序遍历结果列表，里面包含了空指针，如何构造一颗二叉树。\n",
    "# 而前面的题是已已知2个序遍历结果，没有空指针信息，如何构建一颗二叉树\n",
    "\n",
    "# 方法一：前序遍历实现的序列化、反序列化方法。掌握这一种方法就行了。其他两种知道下就行了\n",
    "class Codec:\n",
    "    def __init__(self):\n",
    "        # 用于拼接字符串\n",
    "        self.res = []\n",
    "    \n",
    "    # 先序列化成列表，并带上空指针\n",
    "    # 题目后面有注释说了，ser这个序列化函数的返回结果会自动传递给deser这个函数的\n",
    "    def serialize(self, root):\n",
    "        \"\"\"Encodes a tree to a single string.\n",
    "        \n",
    "        :type root: TreeNode\n",
    "        :rtype: str\n",
    "        \"\"\"\n",
    "        self.traverse(root)\n",
    "\n",
    "        return \"\".join(self.res)\n",
    "    \n",
    "    # 将二叉树打平为字符串\n",
    "    def traverse(self, root):\n",
    "        if not root:\n",
    "            # 定义一个常量，表示空节点，也可以定义成常量放进init里\n",
    "            self.res.append(\"#\")\n",
    "            # 定义一个常量，表示分隔符，也可以定义成常量放进init里\n",
    "            self.res.append(\",\")\n",
    "            return\n",
    "        \n",
    "        self.res.append(str(root.val)) # 这里str的原因是：后面会把list转为str，所以list里的元素都必须为str，而不是部分str部分int会报错的\n",
    "        self.res.append(\",\")\n",
    "\n",
    "        self.traverse(root.left)\n",
    "        self.traverse(root.right)\n",
    "\n",
    "    # 主函数，将字符串反序列化为二叉树结构\n",
    "    def deserialize(self, data):\n",
    "        \"\"\"Decodes your encoded data to tree.\n",
    "        \n",
    "        :type data: str\n",
    "        :rtype: TreeNode\n",
    "        \"\"\"\n",
    "        # data = \"\".join(self.res)\n",
    "        nodes = data.split(\",\")\n",
    "\n",
    "        return self._deserialize(nodes)\n",
    "    \n",
    "    def _deserialize(self, data):\n",
    "        # 如果列表为空，返回空节点\n",
    "        if not data:\n",
    "            return None\n",
    "\n",
    "        # 前序遍历位置\n",
    "        # 列表最左侧就是根节点\n",
    "        root_val = data.pop(0)\n",
    "        if root_val == \"#\": # 遇见空指针,如果是空节点，返回空节点\n",
    "            return None\n",
    "        root = TreeNode(int(root_val))\n",
    "\n",
    "        # 递归地构造左右子树\n",
    "        root.left = self._deserialize(data)\n",
    "        root.right = self._deserialize(data)\n",
    "\n",
    "        # 返回根节点\n",
    "        return root\n",
    "\n",
    "# Your Codec object will be instantiated and called as such:\n",
    "# ser = Codec()\n",
    "# deser = Codec()\n",
    "# ans = deser.deserialize(ser.serialize(root))\n",
    "\n",
    "# 方法二：后序遍历实现的序列化、反序列化方法\n",
    "# class Codec:\n",
    "#     def __init__(self):\n",
    "#         # 用于拼接字符串\n",
    "#         self.res = []\n",
    "    \n",
    "#     # 先序列化成列表，并带上空指针\n",
    "#     # 题目后面有注释说了，ser这个序列化函数的返回结果会自动传递给deser这个函数的\n",
    "#     def serialize(self, root):\n",
    "#         \"\"\"Encodes a tree to a single string.\n",
    "        \n",
    "#         :type root: TreeNode\n",
    "#         :rtype: str\n",
    "#         \"\"\"\n",
    "#         self.traverse(root)\n",
    "\n",
    "#         return \"\".join(self.res)\n",
    "    \n",
    "#     # 将二叉树打平为字符串\n",
    "#     def traverse(self, root):\n",
    "#         if not root:\n",
    "#             # 定义一个常量，表示空节点，也可以定义成常量放进init里\n",
    "#             self.res.append(\"#\")\n",
    "#             # 定义一个常量，表示分隔符，也可以定义成常量放进init里\n",
    "#             self.res.append(\",\")\n",
    "#             return\n",
    "\n",
    "#         self.traverse(root.left)\n",
    "#         self.traverse(root.right)\n",
    "#         self.res.append(str(root.val)) # 这里str的原因是：后面会把list转为str，所以list里的元素都必须为str，而不是部分str部分int会报错的\n",
    "#         self.res.append(\",\")\n",
    "\n",
    "#     # 主函数，将字符串反序列化为二叉树结构\n",
    "#     def deserialize(self, data):\n",
    "#         \"\"\"Decodes your encoded data to tree.\n",
    "        \n",
    "#         :type data: str\n",
    "#         :rtype: TreeNode\n",
    "#         \"\"\"\n",
    "#         nodes = data.split(\",\")\n",
    "\n",
    "#         return self._deserialize(nodes)\n",
    "    \n",
    "#     def _deserialize(self, data):\n",
    "#         # 如果列表为空，返回空节点\n",
    "#         if not data:\n",
    "#             return None\n",
    "\n",
    "#         # 后序遍历位置\n",
    "#         # 列表最右侧就是根节点\n",
    "#         # 这里pop的总是列表最后一个元素。而后序遍历是左子树、右子树、根节点的顺序。\n",
    "#         # 因为pop总的总是最后一个元素，所以pop完根节点之后，就该pop右子树的节点了。所以递归的时候，要先递归右子树，在递归左子树\n",
    "#         root_val = data.pop()\n",
    "#         if root_val == \"#\": # 遇见空指针,如果是空节点，返回空节点\n",
    "#             return None\n",
    "#         root = TreeNode(int(root_val))\n",
    "\n",
    "#         # 递归地构造左右子树\n",
    "#         root.right = self._deserialize(data)\n",
    "#         root.left = self._deserialize(data)\n",
    "        \n",
    "#         # 返回根节点\n",
    "#         return root\n",
    "\n",
    "# # 方法三：层序遍历。我就不写了。也挺好理解的，不用掌握\n",
    "\n",
    "# # 定义一个常量，表示分隔符\n",
    "# SEP = \",\"\n",
    "# # 定义一个常量，表示空节点\n",
    "# NULL = \"#\"\n",
    "\n",
    "# # 定义一个函数，将二叉树序列化为字符串\n",
    "# def serialize(root):\n",
    "#     if root is None: # 如果根节点为空，返回空字符串\n",
    "#         return \"\"\n",
    "#     sb = [] # 定义一个列表，用来存储字符串\n",
    "#     # 初始化队列，将 root 加入队列\n",
    "#     q = [root]\n",
    "    \n",
    "#     while q: # 当队列不为空时，循环执行以下操作\n",
    "#         cur = q.pop(0) # 弹出队列的第一个元素\n",
    "        \n",
    "#         # 层级遍历代码位置\n",
    "#         if cur is None: # 如果当前节点为空\n",
    "#             sb.append(NULL + SEP) # 将空节点的标识符和分隔符加入列表\n",
    "#             continue # 跳过后续操作\n",
    "#         sb.append(str(cur.val) + SEP) # 将当前节点的值和分隔符加入列表\n",
    "#         # 将当前节点的左右子节点加入队列\n",
    "#         q.append(cur.left)\n",
    "#         q.append(cur.right)\n",
    "    \n",
    "#     return \"\".join(sb) # 将列表中的字符串拼接起来，返回结果\n",
    "\n",
    "\n",
    "# # 将字符串反序列化为二叉树结构\n",
    "# def deserialize(data):\n",
    "#     if not data: return None\n",
    "#     nodes = data.split(SEP)\n",
    "#     # 第一个元素就是 root 的值\n",
    "#     root = TreeNode(int(nodes[0]))\n",
    "\n",
    "#     # 队列 q 记录父节点，将 root 加入队列\n",
    "#     q = collections.deque()\n",
    "#     q.append(root)\n",
    "\n",
    "#     i = 1\n",
    "#     while q:\n",
    "#         # 队列中存的都是父节点\n",
    "#         parent = q.popleft()\n",
    "#         # 父节点对应的左侧子节点的值\n",
    "#         left = nodes[i]\n",
    "#         i += 1\n",
    "#         if left != NULL:\n",
    "#             parent.left = TreeNode(int(left))\n",
    "#             q.append(parent.left)\n",
    "#         else:\n",
    "#             parent.left = None\n",
    "#         # 父节点对应的右侧子节点的值\n",
    "#         right = nodes[i]\n",
    "#         i += 1\n",
    "#         if right != NULL:\n",
    "#             parent.right = TreeNode(int(right))\n",
    "#             q.append(parent.right)\n",
    "#         else:\n",
    "#             parent.right = None\n",
    "#     return root\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode(object):\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Codec:\n",
    "\n",
    "    def serialize(self, root):\n",
    "        \"\"\"Encodes a tree to a single string.\n",
    "        \n",
    "        :type root: TreeNode\n",
    "        :rtype: str\n",
    "        \"\"\"\n",
    "        self.alist = []\n",
    "        def preorder(root):\n",
    "            if not root:\n",
    "                self.alist.append('#')\n",
    "                return \n",
    "            self.alist.append(str(root.val))\n",
    "            preorder(root.left)\n",
    "            preorder(root.right)\n",
    "        preorder(root)\n",
    "        return ','.join(self.alist)\n",
    "\n",
    "\n",
    "\n",
    "    def deserialize(self, data):\n",
    "        \"\"\"Decodes your encoded data to tree.\n",
    "        \n",
    "        :type data: str\n",
    "        :rtype: TreeNode\n",
    "        \"\"\"\n",
    "        arr = data.split(',')\n",
    "        alen = len(arr)\n",
    "        if alen == 2:return None\n",
    "        return self.buildTree(arr)\n",
    "    \n",
    "    def buildTree(self,arr):\n",
    "        if arr[0] == '#':\n",
    "            del arr[0]\n",
    "            return None\n",
    "        root = TreeNode(int(arr[0]))\n",
    "        del arr[0]\n",
    "        root.left = self.buildTree(arr)\n",
    "        root.right = self.buildTree(arr)\n",
    "        return root\n",
    "\n",
    "\n",
    "\n",
    "# Your Codec object will be instantiated and called as such:\n",
    "# ser = Codec()\n",
    "# deser = Codec()\n",
    "# ans = deser.deserialize(ser.serialize(root))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode(object):\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Codec:\n",
    "\n",
    "    def serialize(self, root):\n",
    "        \"\"\"Encodes a tree to a single string.\n",
    "        \n",
    "        :type root: TreeNode\n",
    "        :rtype: str\n",
    "        \"\"\"\n",
    "        if not root:\n",
    "            return \"\"\n",
    "        ret=[]\n",
    "        dq=deque([root])\n",
    "        while dq:\n",
    "            node=dq.popleft()\n",
    "            if node:\n",
    "                ret.append(str(node.val))\n",
    "                dq.append(node.left)\n",
    "                dq.append(node.right)\n",
    "            else:\n",
    "                ret.append('None')\n",
    "        return ','.join(ret)\n",
    "\n",
    "    def deserialize(self, data):\n",
    "        \"\"\"Decodes your encoded data to tree.\n",
    "        \n",
    "        :type data: str\n",
    "        :rtype: TreeNode\n",
    "        \"\"\"\n",
    "        if not data:\n",
    "            return\n",
    "        dataList=data.split(',')\n",
    "        root=TreeNode(int(dataList[0]))\n",
    "        dq=deque([root])\n",
    "        i=1\n",
    "        while dq:\n",
    "            node=dq.popleft()\n",
    "            if dataList[i] != 'None':\n",
    "                node.left=TreeNode(int(dataList[i]))\n",
    "                dq.append(node.left)\n",
    "            i+=1\n",
    "            if dataList[i] !='None':\n",
    "                node.right=TreeNode(int(dataList[i]))\n",
    "                dq.append(node.right)\n",
    "            i+=1\n",
    "        return root\n",
    "               \n",
    "\n",
    "\n",
    "# Your Codec object will be instantiated and called as such:\n",
    "# ser = Codec()\n",
    "# deser = Codec()\n",
    "# ans = deser.deserialize(ser.serialize(root))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode(object):\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Codec:\n",
    "\n",
    "    def serialize(self, root):\n",
    "        \"\"\"Encodes a tree to a single string.\n",
    "        \n",
    "        :type root: TreeNode\n",
    "        :rtype: str\n",
    "        \"\"\"\n",
    "        res = []\n",
    "\n",
    "        def preorder(root):\n",
    "            if not root:\n",
    "                res.append('n')\n",
    "                return\n",
    "            res.append(str(root.val))\n",
    "            preorder(root.left)\n",
    "            preorder(root.right)\n",
    "\n",
    "        preorder(root)\n",
    "        return ','.join(res)\n",
    "\n",
    "    def deserialize(self, data):\n",
    "        \"\"\"Decodes your encoded data to tree.\n",
    "        \n",
    "        :type data: str\n",
    "        :rtype: TreeNode\n",
    "        \"\"\"\n",
    "        arr = data.split(',')\n",
    "        arr.reverse()\n",
    "        def preorder():\n",
    "            if not arr:\n",
    "                return\n",
    "            if arr[-1] =='n':\n",
    "                arr.pop()\n",
    "                return\n",
    "            root = TreeNode(int(arr.pop()))\n",
    "            root.left = preorder()\n",
    "            root.right =preorder()\n",
    "            return  root\n",
    "        return preorder()\n",
    "\n",
    "# Your Codec object will be instantiated and called as such:\n",
    "# ser = Codec()\n",
    "# deser = Codec()\n",
    "# ans = deser.deserialize(ser.serialize(root))\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode(object):\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Codec:\n",
    "    def serialize(self, root: Optional[TreeNode]) -> str:\n",
    "        ans = []\n",
    "        def f(node: Optional[TreeNode]) -> None:\n",
    "            if not node:\n",
    "                ans.append('x')\n",
    "                return \n",
    "            ans.append(str(node.val))\n",
    "            f(node.left)\n",
    "            f(node.right)\n",
    "        f(root)\n",
    "        return ','.join(ans)\n",
    "\n",
    "    def deserialize(self, data: str) -> Optional[TreeNode]:\n",
    "        vals = data.split(',')\n",
    "        cnt = 0\n",
    "        def g() -> Optional[TreeNode]:\n",
    "            nonlocal cnt\n",
    "            if vals[cnt] == 'x':\n",
    "                cnt += 1\n",
    "                return None\n",
    "            node = TreeNode(int(vals[cnt]))\n",
    "            cnt += 1\n",
    "            node.left = g()\n",
    "            node.right = g()\n",
    "            return node\n",
    "        return g()\n",
    "            \n",
    "\n",
    "# Your Codec object will be instantiated and called as such:\n",
    "# ser = Codec()\n",
    "# deser = Codec()\n",
    "# ans = deser.deserialize(ser.serialize(root))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode(object):\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Codec:\n",
    "    def serialize(self, root: TreeNode):\n",
    "        \"\"\"\n",
    "        Encodes a tree to a single string.\n",
    "        :type root: TreeNode\n",
    "        :rtype: str\n",
    "        \"\"\"\n",
    "        if root is None:\n",
    "            return ''\n",
    "        return \",\".join(self.level_serialize(root))\n",
    "\n",
    "    def level_serialize(self, root: Optional[TreeNode]):\n",
    "        \"\"\"\n",
    "        前序遍历序列化\n",
    "        \"\"\"\n",
    "        arr = []\n",
    "        first_nodes = [root]\n",
    "        while len(first_nodes) > 0:\n",
    "            second_nodes = []\n",
    "            for node in first_nodes:\n",
    "                if node is None:\n",
    "                    arr.append('#')\n",
    "                    continue\n",
    "                arr.append(str(node.val))\n",
    "                second_nodes.append(node.left)\n",
    "                second_nodes.append(node.right)\n",
    "            first_nodes = second_nodes\n",
    "\n",
    "        return arr\n",
    "\n",
    "    def deserialize(self, data):\n",
    "        \"\"\"\n",
    "        Decodes your encoded data to tree.\n",
    "        :type data: str\n",
    "        :rtype: TreeNode\n",
    "        \"\"\"\n",
    "        if len(data) == 0:\n",
    "            return None\n",
    "        arr = data.split(',')\n",
    "        return self.level_deserialize(arr)\n",
    "\n",
    "    def level_deserialize(self, arr):\n",
    "        root = TreeNode(arr[0])\n",
    "        nodes = [root]\n",
    "        arr.pop(0)\n",
    "        while len(nodes) > 0:\n",
    "            cur_node = nodes.pop(0)\n",
    "            if len(arr) == 0:\n",
    "                break\n",
    "            first_val = arr.pop(0)\n",
    "            if first_val != '#':\n",
    "                node = TreeNode(int(first_val))\n",
    "                cur_node.left = node\n",
    "                nodes.append(node)\n",
    "\n",
    "            first_val = arr.pop(0)\n",
    "            if first_val != '#':\n",
    "                node = TreeNode(int(first_val))\n",
    "                cur_node.right = node\n",
    "                nodes.append(node)\n",
    "        return root\n",
    "        \n",
    "\n",
    "# Your Codec object will be instantiated and called as such:\n",
    "# ser = Codec()\n",
    "# deser = Codec()\n",
    "# ans = deser.deserialize(ser.serialize(root))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode(object):\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Codec:\n",
    "\n",
    "    def serialize(self, root):\n",
    "        \"\"\"Encodes a tree to a single string.\n",
    "        \n",
    "        :type root: TreeNode\n",
    "        :rtype: str\n",
    "        \"\"\"\n",
    "        if not root:\n",
    "            return ''\n",
    "        data_ls = []\n",
    "        string = ''\n",
    "        old_queue = []\n",
    "        new_queue = [root]\n",
    "        while new_queue:\n",
    "            old_queue = new_queue\n",
    "            new_queue = []\n",
    "            while old_queue:\n",
    "                node = old_queue.pop(0)\n",
    "                if node:\n",
    "                    data_ls.append(node.val)\n",
    "                    new_queue.append(node.left)\n",
    "                    new_queue.append(node.right)\n",
    "                else:\n",
    "                    data_ls.append(sys.maxsize)\n",
    "            string += ';'.join(list(map(str, data_ls)))\n",
    "            string += '\\n'\n",
    "            data_ls = []\n",
    "        return string\n",
    "\n",
    "        \n",
    "\n",
    "    def deserialize(self, data):\n",
    "        \"\"\"Decodes your encoded data to tree.\n",
    "        \n",
    "        :type data: str\n",
    "        :rtype: TreeNode\n",
    "        \"\"\"\n",
    "        if data == '':\n",
    "            return None\n",
    "        data_ls = data.split()\n",
    "        root = TreeNode(int(data_ls[0]))\n",
    "        queue = [root]\n",
    "        for data_str in data_ls[1:]:\n",
    "            for index, val in enumerate(data_str.split(';')):\n",
    "                if index % 2 == 0:  \n",
    "                    node = queue.pop(0)\n",
    "                    node.left = TreeNode(int(val)) if val != str(sys.maxsize) else None\n",
    "                    if node.left:\n",
    "                        queue.append(node.left)\n",
    "                else:\n",
    "                    node.right = TreeNode(int(val)) if val != str(sys.maxsize) else None\n",
    "                    if node.right:\n",
    "                        queue.append(node.right)\n",
    "        return root\n",
    "\n",
    "        \n",
    "        \n",
    "\n",
    "# Your Codec object will be instantiated and called as such:\n",
    "# ser = Codec()\n",
    "# deser = Codec()\n",
    "# ans = deser.deserialize(ser.serialize(root))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode(object):\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Codec:\n",
    "\n",
    "    def serialize(self, root):\n",
    "        \"\"\"Encodes a tree to a single string.\n",
    "        \n",
    "        :type root: TreeNode\n",
    "        :rtype: str\n",
    "        \"\"\"\n",
    "        if not root:\n",
    "            return '[]'\n",
    "        queue = [root]\n",
    "        ans = []\n",
    "        a = []\n",
    "\n",
    "        while queue:\n",
    "            cur = queue.pop(0)\n",
    "            if cur: \n",
    "                ans.append(cur.val)\n",
    "                queue.append(cur.left)\n",
    "                queue.append(cur.right)\n",
    "            else:\n",
    "                ans.append(1001)\n",
    "\n",
    "        print(ans)\n",
    "        return str(ans)\n",
    "        \n",
    "\n",
    "    def deserialize(self, data):\n",
    "        \"\"\"Decodes your encoded data to tree.\n",
    "        \n",
    "        :type data: str\n",
    "        :rtype: TreeNode\n",
    "        \"\"\"\n",
    "        data = data.strip('[]')\n",
    "        datas = data.split(',')\n",
    "        if datas == [''] or int(datas[0]) == 1001:\n",
    "            return []\n",
    "        root = TreeNode(int(datas[0]))\n",
    "        queue = [root]\n",
    "\n",
    "\n",
    "        for i in range(len(datas) // 2):\n",
    "            left = int(datas[i * 2 + 1])\n",
    "            right = int(datas[ i * 2 + 2])\n",
    "            cur = queue.pop(0)\n",
    "            if left != 1001:\n",
    "                cur.left = TreeNode(int(left))\n",
    "                queue.append(cur.left)\n",
    "            if right != 1001:\n",
    "                cur.right = TreeNode(int(right))\n",
    "                queue.append(cur.right)\n",
    "        return root\n",
    "\n",
    "# Your Codec object will be instantiated and called as such:\n",
    "# ser = Codec()\n",
    "# deser = Codec()\n",
    "# ans = deser.deserialize(ser.serialize(root))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode(object):\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Codec:\n",
    "    def _s2i(self, s):\n",
    "        f = 1\n",
    "        if s[0] == '-':\n",
    "            f, s = -1, s[1:]\n",
    "        k = 0\n",
    "        while (len(s) > 0) and (s[0] not in ('[','n',']')):\n",
    "            k = k * 10 + int(s[0])\n",
    "            s = s[1:]\n",
    "        return (k*f, s)\n",
    "    \n",
    "    def serialize(self, root: TreeNode) -> str:\n",
    "        if root is None:\n",
    "            return 'n'\n",
    "        s = \"\"\n",
    "        if root.right:\n",
    "            s = self.serialize(root.right)\n",
    "        if root.left or s != \"\":\n",
    "            s = self.serialize(root.left) + s\n",
    "        return \"[%d%s]\" % (root.val, s)\n",
    "\n",
    "    def _des(self, data:str) -> (TreeNode, str):\n",
    "        if data[0] == 'n':\n",
    "            return None, data[1:]\n",
    "        if data[0] == ']':\n",
    "            return None, data\n",
    "        assert(data[0]=='[')\n",
    "        data = data[1:]\n",
    "        v, data = self._s2i(data)\n",
    "        left, data = self._des(data)\n",
    "        right, data = self._des(data)\n",
    "        assert(data[0] == ']')\n",
    "        return TreeNode(v,left,right), data[1:]\n",
    "        \n",
    "    def deserialize(self, data: str) -> TreeNode:\n",
    "        root, _ = self._des(data)\n",
    "        return root\n",
    "        \n",
    "\n",
    "# Your Codec object will be instantiated and called as such:\n",
    "# ser = Codec()\n",
    "# deser = Codec()\n",
    "# ans = deser.deserialize(ser.serialize(root))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode(object):\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Codec:\n",
    "    def __init__(self):\n",
    "        self.flag = 0\n",
    "\n",
    "    def f(self, root, data):\n",
    "        if root is None:\n",
    "            data += '#,'\n",
    "            return data\n",
    "        data += str(root.val)+','\n",
    "        data = self.f(root.left, data)\n",
    "        data = self.f(root.right, data)\n",
    "        return data\n",
    "\n",
    "    \n",
    "    def serialize(self, root):\n",
    "        \"\"\"Encodes a tree to a single string.\n",
    "        \n",
    "        :type root: TreeNode\n",
    "        :rtype: str\n",
    "        \"\"\"\n",
    "        return self.f(root, '')\n",
    "        \n",
    "    def g(self, val):\n",
    "        if val[self.flag]=='#':\n",
    "            self.flag += 1\n",
    "            return None\n",
    "        p = TreeNode(val[self.flag])\n",
    "        self.flag += 1\n",
    "        p.left = self.g(val)\n",
    "        p.right = self.g(val)\n",
    "        return p\n",
    "\n",
    "    def deserialize(self, data):\n",
    "        \"\"\"Decodes your encoded data to tree.\n",
    "        \n",
    "        :type data: str\n",
    "        :rtype: TreeNode\n",
    "        \"\"\"\n",
    "        return self.g(data.split(','))\n",
    "\n",
    "# Your Codec object will be instantiated and called as such:\n",
    "# ser = Codec()\n",
    "# deser = Codec()\n",
    "# ans = deser.deserialize(ser.serialize(root))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode(object):\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Codec:\n",
    "\n",
    "    def serialize(self, root, str1 = \"\"):\n",
    "        \"\"\"Encodes a tree to a single string.\n",
    "        \n",
    "        :type root: TreeNode\n",
    "        :rtype: str\n",
    "        \"\"\"\n",
    "        if root is None:\n",
    "            str1 += \"None,\" \n",
    "        else:\n",
    "            str1 = str(str1) + str(root.val) + \",\"\n",
    "            str1 = self.serialize(root.left, str1)\n",
    "            str1 = self.serialize(root.right, str1)\n",
    "        return str1\n",
    "        \n",
    "\n",
    "    def deserialize(self, data):\n",
    "        print(data)\n",
    "        \"\"\"Decodes your encoded data to tree.\n",
    "        \n",
    "        :type data: str\n",
    "        :rtype: TreeNode\n",
    "        \"\"\"\n",
    "        root, data = self.deserialize_data(data)\n",
    "        return root\n",
    "    \n",
    "    def deserialize_data(self, data):\n",
    "        \"\"\"Decodes your encoded data to tree.\n",
    "        \n",
    "        :type data: str\n",
    "        :rtype: TreeNode\n",
    "        \"\"\"\n",
    "        val = data.split(\",\")[0]\n",
    "        if val == \"None\":\n",
    "            data = data.lstrip(val)\n",
    "            data = data.lstrip(\",\")\n",
    "            return None, data\n",
    "        root = TreeNode(val)\n",
    "        data = data.lstrip(val)\n",
    "        data = data.lstrip(\",\")\n",
    "        root.left, data = self.deserialize_data(data)\n",
    "        root.right, data = self.deserialize_data(data)\n",
    "        return root, data\n",
    "\n",
    "        \n",
    "\n",
    "# Your Codec object will be instantiated and called as such:\n",
    "# ser = Codec()\n",
    "# deser = Codec()\n",
    "# ans = deser.deserialize(ser.serialize(root))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode(object):\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Codec:\n",
    "\n",
    "    def serialize(self, root):\n",
    "        \"\"\"Encodes a tree to a single string.\n",
    "        \n",
    "        :type root: TreeNode\n",
    "        :rtype: str\n",
    "        \"\"\"\n",
    "        return self.rserialize(root, \"\")\n",
    "\n",
    "    def rserialize(self, node, s):\n",
    "\n",
    "        if not node: return s + \"None,\"\n",
    "        s += f\"{node.val},\"\n",
    "        s = self.rserialize(node.left, s)\n",
    "        s = self.rserialize(node.right, s)\n",
    "        return s\n",
    "\n",
    "\n",
    "    def deserialize(self, data):\n",
    "        \"\"\"Decodes your encoded data to tree.\n",
    "        \n",
    "        :type data: str\n",
    "        :rtype: TreeNode\n",
    "        \"\"\"\n",
    "        if data[0] == \"None\": return None\n",
    "        self.data = data.split(\",\")[:-1]\n",
    "        return self.rdeserialize(self.data)\n",
    "\n",
    "    def rdeserialize(self, data):\n",
    "        if self.data[0] == \"None\":\n",
    "            self.data.pop(0)\n",
    "            return None\n",
    "        node = TreeNode(int(self.data.pop(0)))\n",
    "        node.left = self.rdeserialize(self.data)\n",
    "        node.right = self.rdeserialize(self.data)\n",
    "\n",
    "        return node        \n",
    "\n",
    "# Your Codec object will be instantiated and called as such:\n",
    "# ser = Codec()\n",
    "# deser = Codec()\n",
    "# ans = deser.deserialize(ser.serialize(root))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode(object):\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Codec:\n",
    "\n",
    "    def serialize(self, root):\n",
    "        \"\"\"Encodes a tree to a single string.\n",
    "        \n",
    "        :type root: TreeNode\n",
    "        :rtype: str\n",
    "        \"\"\"\n",
    "        def dfs(node,s):\n",
    "            if not node: \n",
    "                s+='None,'\n",
    "                return s\n",
    "            s=s+str(node.val)+','\n",
    "            s=dfs(node.left,s)\n",
    "            s=dfs(node.right,s)\n",
    "            return s\n",
    "       \n",
    "        return dfs(root,'')\n",
    "\n",
    "        \n",
    "\n",
    "    def deserialize(self, data):\n",
    "        \"\"\"Decodes your encoded data to tree.\n",
    "        \n",
    "        :type data: str\n",
    "        :rtype: TreeNode\n",
    "        \"\"\"\n",
    "        nums=data.split(',')\n",
    "        nums.pop(-1)\n",
    "        def dfs(nums):\n",
    "            tmp=nums.pop(0)\n",
    "            if tmp=='None':\n",
    "                return None\n",
    "            node=TreeNode(int(tmp))\n",
    "            node.left=dfs(nums)\n",
    "            node.right=dfs(nums)\n",
    "            return node\n",
    "        return dfs(nums)\n",
    "\n",
    "        \n",
    "        \n",
    "        \n",
    "\n",
    "\n",
    "\n",
    "        \n",
    "\n",
    "# Your Codec object will be instantiated and called as such:\n",
    "# ser = Codec()\n",
    "# deser = Codec()\n",
    "# ans = deser.deserialize(ser.serialize(root))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode(object):\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Codec:\n",
    "\n",
    "    def serialize(self, root):\n",
    "        \"\"\"Encodes a tree to a single string.\n",
    "        \n",
    "        :type root: TreeNode\n",
    "        :rtype: str\n",
    "        \"\"\"\n",
    "        return self.rserialize(root, \"\")\n",
    "\n",
    "    def rserialize(self, node, s):\n",
    "\n",
    "        if not node: return s + \"None,\"\n",
    "        s += f\"{node.val},\"\n",
    "        s = self.rserialize(node.left, s)\n",
    "        s = self.rserialize(node.right, s)\n",
    "        return s\n",
    "\n",
    "\n",
    "    def deserialize(self, data):\n",
    "        \"\"\"Decodes your encoded data to tree.\n",
    "        \n",
    "        :type data: str\n",
    "        :rtype: TreeNode\n",
    "        \"\"\"\n",
    "        if data[0] == \"None\": return None\n",
    "        self.data = data.split(\",\")[:-1]\n",
    "        return self.rdeserialize(self.data)\n",
    "\n",
    "    def rdeserialize(self, data):\n",
    "        if self.data[0] == \"None\":\n",
    "            self.data.pop(0)\n",
    "            return None\n",
    "        node = TreeNode(int(self.data.pop(0)))\n",
    "        node.left = self.rdeserialize(self.data)\n",
    "        node.right = self.rdeserialize(self.data)\n",
    "\n",
    "        return node        \n",
    "\n",
    "# Your Codec object will be instantiated and called as such:\n",
    "# ser = Codec()\n",
    "# deser = Codec()\n",
    "# ans = deser.deserialize(ser.serialize(root))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode(object):\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Codec:\n",
    "\n",
    "    def serialize(self, root):\n",
    "        \"\"\"Encodes a tree to a single string.\n",
    "        \n",
    "        :type root: TreeNode\n",
    "        :rtype: str\n",
    "        \"\"\"\n",
    "        def dfs(node,s):\n",
    "            if not node: \n",
    "                s+='None,'\n",
    "                return s\n",
    "            s=s+str(node.val)+','\n",
    "            s=dfs(node.left,s)\n",
    "            s=dfs(node.right,s)\n",
    "            return s\n",
    "        res=dfs(root,'')\n",
    "        return res\n",
    "        \n",
    "\n",
    "    def deserialize(self, data):\n",
    "        \"\"\"Decodes your encoded data to tree.\n",
    "        \n",
    "        :type data: str\n",
    "        :rtype: TreeNode\n",
    "        \"\"\"\n",
    "        \n",
    "        nums=data.split(',')\n",
    "        nums.pop(-1)\n",
    "        if nums[0]=='None': return None\n",
    "\n",
    "        def dfs(nums):\n",
    "            if not nums: \n",
    "                return \n",
    "            if nums[0]==\"None\": \n",
    "                nums.pop(0)\n",
    "                return None\n",
    "            cur=TreeNode(int(nums[0]))\n",
    "            nums.pop(0)\n",
    "            \n",
    "            cur.left=dfs(nums)\n",
    "            \n",
    "\n",
    "            cur.right=dfs(nums)\n",
    "            return cur\n",
    "        return dfs(nums)\n",
    "\n",
    "\n",
    "\n",
    "        \n",
    "\n",
    "# Your Codec object will be instantiated and called as such:\n",
    "# ser = Codec()\n",
    "# deser = Codec()\n",
    "# ans = deser.deserialize(ser.serialize(root))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode(object):\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Codec:\n",
    "\n",
    "    def serialize(self, root):\n",
    "        \"\"\"Encodes a tree to a single string.\n",
    "        \n",
    "        :type root: TreeNode\n",
    "        :rtype: str\n",
    "        \"\"\"\n",
    "        if not root:\n",
    "            return \"\"\n",
    "        \n",
    "        l = [[(1, root)]]\n",
    "        while 1:\n",
    "            now = []\n",
    "            for n, node in l[-1]:\n",
    "                if node.left:\n",
    "                    now.append((n * 2, node.left))\n",
    "                if node.right:\n",
    "                    now.append((n * 2 + 1, node.right))\n",
    "            if now:\n",
    "                l.append(now)\n",
    "            else:\n",
    "                break\n",
    "        \n",
    "        ret = \"\"\n",
    "        for row in l:\n",
    "            now = []\n",
    "            for n, node in row:\n",
    "                now.append((n, node.val))\n",
    "            ret += \"\\0\" + str(now)\n",
    "        return ret[1:]\n",
    "\n",
    "\n",
    "    def deserialize(self, data):\n",
    "        \"\"\"Decodes your encoded data to tree.\n",
    "        \n",
    "        :type data: str\n",
    "        :rtype: TreeNode\n",
    "        \"\"\"\n",
    "        if not data:\n",
    "            return\n",
    "\n",
    "        l = [eval(e) for e in data.split(\"\\0\")]\n",
    "        root = TreeNode(l[0][0][1])\n",
    "        d = {1: root}\n",
    "\n",
    "        for i in range(1, len(l)):\n",
    "            for n, val in l[i]:\n",
    "                node = TreeNode(val)\n",
    "                d[n] = node\n",
    "\n",
    "                if n % 2:\n",
    "                    d[n // 2].right = node\n",
    "                else:\n",
    "                    d[n // 2].left = node\n",
    "\n",
    "        return root\n",
    "        \n",
    "\n",
    "# Your Codec object will be instantiated and called as such:\n",
    "# ser = Codec()\n",
    "# deser = Codec()\n",
    "# ans = deser.deserialize(ser.serialize(root))"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
